Skip to main content

Section 5.5 Challenge Problems

  1. Fix \(d\geq1\text{.}\) Given a set \(X\subseteq \mathbb{R}^d\text{,}\) a vector \(\vec{p}\in\mathbb{R}^d\) and \(r\in \mathbb{R}\text{,}\) define
    \begin{equation*} \vec{p}+rX := \{\vec{p}+r\vec{x}: \vec{x}\in X\}\text{.} \end{equation*}
    Given sets \(X_1\) and \(X_2\text{,}\) say that \(X_1\) is homothetic to \(X_2\) if there exist \(\vec{p}\in\mathbb{R}^d\) and \(r>0\) such that \(X_2=\vec{p}+rX_1\text{.}\) Say that a set \(A\subseteq \mathbb{R}^d\) is \(X\)-free if it does not contain any subset that is homothetic to \(X\text{.}\) Using Behrend’s Theorem (see Exercise 10 from Section 5.4), prove that for any set \(X\subseteq\mathbb{R}^d\) with \(|X|\geq3\text{,}\) there exists \(c>0\) such that, for every \(n\geq1\text{,}\) there exists an \(X\)-free set \(A\subseteq [n]^d\) satisfying
    \begin{equation*} |A|\geq n^d\cdot \exp(-c\sqrt{\log{n}})\text{.} \end{equation*}
  2. Recall that \(\alpha(G)\) is the cardinality of the largest independent set in \(G\) (i.e. the largest set of vertices containing no edges). Show that if \(G\) is a \(K_4\)-free graph with \(n\) vertices satisfying \(\alpha(G)=o(n)\text{,}\) then
    \begin{equation*} |E(G)| \leq \left(1/8+o(1)\right)n^2. \end{equation*}
  3. Find an example of a \(K_4\)-free graph with \(n\) vertices satisfying \(\alpha(G)=o(n)\) and
    \begin{equation*} |E(G)| \geq \left(1/8-o(1)\right)n^2. \end{equation*}