## Section 3.6 Exercises

- Show that, if \(G\) is a triangle-free graph, then \(\alpha(G)\geq \Delta(G)\text{.}\)
- Prove that, for every graph \(G\text{,}\)\begin{equation*} \alpha(G)\geq \sum_{v\in V(G)}\frac{1}{d(v)+1}\text{.} \end{equation*}
- Use question 2.a to prove Turán’s Theorem.

- For \(r\geq2\text{,}\) suppose that \(G\) is a graph which does not contain \(K_r\text{.}\) Prove that there exists a graph \(G'\) with \(V(G')=V(G)\) such that \(\chi(G')\leq r-1\) and\begin{equation*} d_{G'}(v)\geq d_G(v) \end{equation*}for all \(v\in V(G)\text{.}\) Deduce Turán’s Theorem.
*Hint:*Consider a vertex of maximum degree. Induct on \(r\text{.}\) - A
*\(k\)-cycle*in a digraph is a sequence of \(k\) vertices \((v_0,v_1,\dots,v_{k-1})\) such that the edge \(v_iv_{i+1}\) is oriented from \(v_i\) to \(v_{i+1}\) for all \(0\leq i\leq k-1\) (viewing indices modulo \(k\)). Prove that the number of \(3\)-cycles in every digraph on \(n\) vertices is at most \(\frac{1}{4}\binom{n+1}{3}\text{.}\)*Hint:*Without loss of generality, the digraph is a tournament. - A tournament is said to be
*transitive*if the vertices can be ordered \(v_1,v_2,\dots,v_n\) such that, if \(i\lt j\text{,}\) then the edge \(v_iv_j\) is oriented from \(v_i\) to \(v_j\text{.}\) Prove that every tournament on \(n\) vertices contains a transitive tournament with at least \(\lfloor \log_2(n)\rfloor +1\) vertices. - Given \(n\) irrational numbers \(x_1,\dots,x_n\text{,}\) let \(f(x_1,\dots,x_n)\) be the number of unordered pairs \(\{x_i,x_j\}\) such that \(x_i+x_j\) is rational. Determine the maximum value of \(f(x_1,\dots,x_n)\) among all choices of \(x_1,\dots,x_n\in \mathbb{R}\setminus \mathbb{Q}\text{.}\)
- In the proof of Mantel’s Theorem, we showed that \(\sum_{v\in V(G)}\degree(v)^2\leq |E(G)||V(G)|\) for any triangle-free graph \(G\text{.}\) Prove that, for any graph \(G\) (with or without triangles),\begin{equation*} \sum_{v\in V(G)}\degree(v)^2\leq 2|E(G)|(|V(G)|-1)\text{.} \end{equation*}For which graphs \(G\) is this inequality tight?
- A
*permutation*of \([n]\) is a bijection \(\pi:[n]\to[n]\text{.}\) We often express a permutation \(\pi\) as a sequence \((\pi(1),\dots,\pi(n))\text{.}\) For example, \((1,3,2)\) is a permutation of \([3]\text{.}\) The*displacement*of a permutation \(\pi\) of \([n]\) is defined to be \(\sum_{i=1}^n|\pi(i)-i|\text{.}\) Prove that every permutation \(\pi\) of \([n]\) has displacement at most \(n^2/2\text{.}\) normalized appropriately.} } - Given a permutation \(\sigma\) of \([k]\) and a permutation \(\pi\) of \([n]\) where \(k\leq n\text{,}\) a
*copy*of \(\sigma\) in \(\pi\) is a subsequence \((a(1),\dots,a(k))\) of \((\pi(1),\dots,\pi(n))\) such that \(a(i)\lt a(j)\) if and only if \(\sigma(i)\lt \sigma(j)\) for \(1\leq i,j\leq k\text{.}\) Let \(\#(\sigma,\pi)\) denote the number of copies of \(\sigma\) in \(\pi\) and define \(\#(\sigma,n)\) to be the maximum of \(\#(\sigma,\pi)\) over all permutations \(\pi\) of \([n]\text{.}\) The*packing density*of \(\sigma\) is\begin{equation*} p(\sigma):=\lim_{n\to\infty} \frac{\#(\sigma,n)}{\binom{n}{k}}\text{.} \end{equation*}- Prove that \(p(\sigma)\) is well-defined (i.e. that the limit exists).
- By coming up with an explicit construction of permutations \(\pi_1,\pi_2,\dots\) whose lengths tend to infinity, prove a lower bound on \(p(1,3,2)\text{.}\) Try to make this lower bound as large as you can.
- (Not easy!) Prove that your construction from the previous part is optimal.

- Let \(M_k\) be the graph consisting of a matching with \(k\) edges. Prove that\begin{equation*} \ex(n,M_k) = \binom{k-1}{2}+(k-1)(n-k+1) \end{equation*}for all \(n\geq 3k\text{.}\)
- Prove Claim 3.2.4.
- Prove that the maximum number of edges in a complete \((r-1)\)-partite graph with \(n\geq r-1\) vertices is attained with all parts are of cardinality \(\lfloor n/(r-1)\rfloor\) or \(\lceil n/(r-1)\rceil\text{.}\) }
- Given graphs \(F\) and \(H\text{,}\) let \(\ex(F,H)\) be the maximum number of edges in a subgraph of \(F\) which does not contain a copy of \(H\text{.}\) Let Qd be the
*\(d\)-dimensional hypercube*; i.e. the graph with vertex set \(\{0,1\}^d\) in which two vertices are adjacent if they differ in a unique coordinate. Prove that\begin{equation*} \ex(Q_d,C_4)\geq |E(Q_d)|/2\text{.} \end{equation*} - Given a graph \(G\) and an edge \(uv\) of \(G\text{,}\) to
*contract*the edge \(uv\) means to replace \(u\) and \(v\) by a single vertex which is adjacent to every vertex that is adjacent to at least one of \(u\) or \(v\text{.}\) We say that \(H\) is a*minor*of \(G\) if it is possible to obtain \(H\) from \(G\) by sequentially contracting edges and deleting vertices or edges.- Suppose that \(c\) is an integer and \(G\) is a graph with \(|E(G)|\geq c|V(G)|\) such that every minor \(H\) of \(G\) satisfies \(|E(H)|\lt c|V(H)|\text{.}\) Prove that any two vertices of \(G\) have at least \(c\) common neighbours.
- Show that every graph \(G\) satisfying \(|E(G)|\geq 2^{k-2}|V(G)|\) contains \(K_k\) as a minor.
*Hint:*Induction on \(k\) and \(|V(G)|\text{.}\)

- Suppose that you have a TV remote control and a box of 8 batteries. The remote requires 2 charged batteries in order to function—i.e. if one or more of the batteries is dead, then it will not work. You know that 4 of the batteries in the box are charged and 4 are dead, but you do not know which are which. How many pairs of batteries do you need to test in order to guarantee that one of the tests is successful?
- Compute \(\ex(n,C_5)\) for \(n\in\{1,2,3,4,5,6\}\text{.}\)
- Show that, for any graph \(H\text{,}\) the sequence \(\ex(n,H)/\binom{n}{2}\) for \(n\geq2\) is non-increasing.
- Prove Proposition 3.3.9.

- For each \(n\text{,}\) let \(g(n)\) be the maximum number of edges in a graph \(G\) on \(n\) vertices such that the edges of \(G\) can be coloured in two colours in such a way that there are no monochromatic triangles.
- Prove that \(\frac{g(n)}{\binom{n}{2}}\) converges as \(n\to\infty\text{.}\)
- Determine \(\lim_{n\to\infty}\frac{g(n)}{\binom{n}{2}}\text{.}\)

- Show that there exists a constant \(C>0\) and a graph \(H\) such that \(\chi(H)=3\) and, for every \(n\text{,}\)\begin{equation*} \ex(n,H)\geq \frac{n^2}{4} + Cn^{3/2}\text{.} \end{equation*}
*Hint 1:*Example 3.4.4 may be helpful.*Hint 2:*For every integer \(m\geq1\text{,}\) there is a prime between \(m\) and \(2m\) (this is known as Bertrand’s Postulate). - For positive integers \(n,s,t\text{,}\) let z(n,s,t) be the maximum number of edges in a subgraph of \(K_{n,n}\) without a copy of \(K_{s,t}\text{.}\) Prove that \(2\ex(n,K_{s,t})\leq z(n,s,t)\leq \ex(2n,K_{s,t})\text{.}\)
- Let \(p\) be a prime and let \(G_p\) be a graph with vertex set\begin{equation*} V(G_p):=\{(x,y,z)\in \mathbb{Z}_p^3: x\neq y, x\neq z, y\neq z\} \end{equation*}where \((x_1,y_1,z_1)\) is adjacent to \((x_2,y_2,z_2)\) if and only if\begin{equation*} (x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2\equiv 1\bmod p\text{.} \end{equation*}
- Determine \(|V(G_p)|\) as a function of \(p\) for all \(p\text{.}\)
- Prove that every vertex in \(G_p\) has degree \(p^2-p\text{.}\)
- Show that \(G_p\) does not contain a copy of \(K_{3,3}\text{.}\)
- Conclude that \(\ex(K_{3,3},n)=\Theta(n^{5/3})\text{.}\) (Hint: Use Bertrand’s Postulate; see the second hint to Exercise 19 in this section).

- Determine \(\ex(n,C_n)\) for all \(n\geq3\text{.}\)
*Hint:*Look up Ore’s Theorem on Hamilton cycles in graphs. - Prove that, for each \(k\geq2\) and \(n\geq1\text{,}\)\begin{equation*} \ex(n,\{C_3,C_4,C_5,\dots,C_{2k}\})\leq n\left(n^{1/k}+1\right)\text{.} \end{equation*}
- Determine \(\ex\left(n,\left\{C_{2k}:k\geq2\right\}\right)\) for every \(n\text{.}\)
- Let \(G\) be a bipartite graph with bipartition \((A_1,A_2)\) and let \(d_i=e(G)/|A_i|\) for \(i\in\{1,2\}\text{.}\) Prove that there is a subgraph \(G'\) of \(G\) such that \(|E(G')|\geq \|E(G)|/2\) and, for \(i\in\{1,2\}\text{,}\) every vertex \(v\in A_i\cap V(G')\) has degree at least \(d_i/4\) in \(G'\text{.}\)
- A
*tree*is a connected graph with no cycles. Show that, for every tree \(T\text{,}\) there exist a constant \(c=c(T)\geq0\) such that \(\ex(n,T)\leq cn\) for all \(n\geq1\text{.}\)*Hint:*Every tree on at least 2 vertices has a vertex of degree one (called a*leaf*). - Determine \(\ex(n,P_k)\) for every \(n\) and \(k\text{.}\)
- Let \(G\) be a \(C_4\)-free bipartite graph with parts of sizes \(n\geq1\) and \(m\geq1\text{.}\) Show that \(G\) has at most \(nm^{1/2}+m\) edges.
- A set \(A\subseteq \mathbb{N}\) is called a
*Sidon set*if \(a,b,c,d\in A\) such that \(a+b=c+d\text{,}\) then \(\{a,b\}=\{c,d\}\text{.}\)- Prove that if \(A\) is a Sidon set such that \(A\subseteq [n]\text{,}\) then\begin{equation*} |A|+\binom{|A|}{2}\leq 2n-1\text{.} \end{equation*}Conclude that \(|A|\lt 2\sqrt{n}\text{.}\)
- Prove that, if \(A\subseteq [n]\) is a Sidon set and \(|A|\lt n^{1/3}\text{,}\) then there exists \(x\in [n]\setminus A\) such that \(A\cup\{x\}\) is a Sidon set.
- Let \(A\subseteq [n]\) be a Sidon set. Let \(G\) be a graph on vertex set \(\{u_1,\dots,u_n\}\cup\{v_1,\dots,v_{2n}\}\) where \(u_iv_j\in E(G)\) if there exists \(a\in A\) such that \(i+a=j\text{.}\) Show that \(G\) does not contain any \(4\)-cycles.

- Let \(G\) be a graph with vertex set \(\{v_1,\dots,v_n\}\) and let \(x_1,\dots,x_n\) be \(n\) real variables. Let \(x=(x_1,\dots,x_n)\in \mathbb{R}^n\text{.}\) Define\begin{equation*} f(x) = \sum_{v_iv_j\in E(G)}x_ix_j\text{.} \end{equation*}Let \(S=\{x\in [0,1]^n: x_1+\cdots+x_n=1\}\) and define \(\rho:=\max_{x\in S}f(x)\text{.}\)
- Prove that the maximum of \(f(x)\) for \(x\in S\) is attained when the non-zero coordinates of \(x\) correspond to the vertices of a clique in \(G\text{.}\) In other words, prove that there exists a clique \(C\subseteq\{v_1,\dots,v_n\}\) and a vector \(x\in S\) such that \(x_i=0\) for all \(v_i\notin S\) and \(f(x)=\rho\text{.}\)
- Prove that \(\rho=\frac{1}{2}\left(1-\frac{1}{r}\right)\) where \(r\) is the number of vertices in the largest clique in \(G\text{.}\)
- Prove that there exists a vector \(x\in S\) such that \(x_i>0\) for all \(i\) and \(f(x)=\rho\) if and only if \(G\) is a complete multipartite graph.
- Use question 30.b and question 30.c to prove Turán’s Theorem by induction on \(n-\lfloor n/r\rfloor\text{.}\)

- Let \(S\) be a set of \(n\) points in a circular region with radius \(1\text{.}\) Prove that the number of pairs \(x,y\in S\) such that the Euclidean distance from \(x\) to \(y\) is at least \(\sqrt{2}\) is at most \(n^2/3\text{.}\)
- Let \(f(n)\) be the minimum size of a family \(\mathcal{F}\) of subsets of \([n]\) such that, for every set \(S\subseteq [n]\) with \(|S|\leq 3\text{,}\) there exists \(A,B\in \mathcal{F}\) such that \(A\cup B=S\) (note: we allow the case \(A=B\)). Prove that \(f(n)=1+n+\binom{n}{2}-\left\lfloor\frac{n^2}{4}\right\rfloor\text{.}\)
- An \(r\)-uniform hypergraph \(H=(V,E)\) is
*r-partite hypergraph*if its vertices can be partitioned into \(r\) sets \(A_1,\dots,A_r\) such that \(|e\cap A_i|=1\) for every \(e\in E\) and \(1\leq i\leq r\text{.}\) Prove that every \(r\)-uniform hypergraph \(H=(V,E)\) has an \(r\)-partite subhypergraph with at least \(\frac{r!}{r^r}|E|\) hyperedges. - For \(r\geq2\) and \(n\geq1\text{,}\) the
*complete hypergraph*\(r\)-uniform hypergraph on \(n\) vertices, denoted Knr, is the hypergraph with vertex set \([n]\) and edge set \(\binom{[n]}{r}\text{.}\) Here, we analyze a well-known construction in the area of hypergraph Turán problems. Let \(n\) be divisible by \(3\) and let \(V_0,V_1,V_2\) be disjoint sets of cardinality \(n/3\text{.}\) Define \(V:= V_0\cup V_1\cup V_2\) and let \(H\) be a \(3\)-uniform hypergraph with vertex set \(V\) such that \(e\in E(H)\) if and only if either (i) \(|e\cap V_i|=1\) for all \(i\in\{0,1,2\}\) or (ii) there exists \(i\in \{0,1,2\}\) such that \(|e\cap V_i|=2\) and \(|e\cap V_{i+1}|=1\text{,}\) where the indices are viewed modulo \(3\text{.}\)- Prove that \(|E(H)|\sim \frac{5}{9}\binom{n}{3}\text{.}\)
- Prove that \(H\) does not contain a copy of \(K_4^{(3)}\text{.}\)

- Our goal is to show that if \(H\) is a \(3\)-uniform hypergraph on \(n\) vertices with no copy of \(K_4^{(3)}\text{,}\) then \(|E(H)|\leq \frac{2n-3}{9}\binom{n}{2}\text{.}\)
- For distinct \(x,y\in V(H)\text{,}\) let \(N(x,y) = \{z\in V(H): \{x,y,z\}\in E(H)\}\) and \(d(x,y)=|N(x,y)|\text{.}\) Prove that if \(\{u,v,w\}\in E(H)\text{,}\) then \(N(u)\cap N(v)\cap N(w)=\emptyset\text{.}\) Use this to show that, if \(\{u,v,w\}\in E(H)\text{,}\) then \(d(u)+d(y)+d(z)\leq 2n-3\text{.}\)
- By summing over all \(e\in E(H)\text{,}\) prove that\begin{equation*} \sum_{\{x,y\}\in \binom{V(H)}{2}} d(x,y)^2 \leq (2n-3)|E(H)|\text{.} \end{equation*}
- Prove that the left side of the inequality in the previous part of the question is at least \(\frac{9|E(H)|^2}{\binom{n}{2}}\text{.}\) Conclude that \(|E(H)|\leq \frac{2n-3}{9}\binom{n}{2}\text{.}\)

- For \(r\geq2\text{,}\) \(k\geq 1\) and \(m\geq1\text{,}\) let \(K_{k}^{(r)}(m)\) be an \(r\)-uniform hypergraph whose vertices are partitioned into \(k\) classes \(A_1,A_2,\dots,A_k\text{,}\) each of cardinality \(m\text{,}\) and whose hyperedges are precisely the sets \(e\) of cardinality three such that \(|e\cap A_i|\leq1\) for \(1\leq i\leq n\text{.}\) Given an \(r\)-uniform hypergraph \(H\) and \(n\geq1\text{,}\) let \(\ex(n,H)\) be the maximum number of hyperedges in an \(r\)-uniform hypergraph on \(n\) vertices which does not contain a copy of \(H\text{.}\)
- Prove that\begin{equation*} \ex\left(n,K_{r}^{(r)}(m)\right)=O\left(n^{r-\frac{1}{m^{r-1}}}\right)\text{.} \end{equation*}
- Let \(K_r(m)\) denote the complete \(r\)-partite graph with parts of size \(m\text{.}\) Using question 36.a, prove that, for every \(\varepsilon>0\text{,}\) there exists \(\delta>0\) such that if \(G\) is a graph containing at least \(\varepsilon\binom{n}{r}\) copies of \(K_r\text{,}\) then \(G\) has at least \(\delta\binom{n}{rm}\) copies of \(K_r(m)\text{.}\)

- Define a notion of
*Turán density*for \(k\)-uniform hypergraphs that is analogous to Definition 3.3.8.- Prove that your definition of the Turán density of a hypergraph is well-defined.
- What do Exercise 34, Exercise 35 and Exercise 36 in this section say about the Turán density of \(K_4^{(3)}\) and \(K_{r}^{(r)}(m)\text{?}\)

- For \(n\geq1\text{,}\) let \(X\) and \(Y\) be independent identically distributed random variables in \(\mathbb{R}^n\text{.}\) Prove that\begin{equation*} \mathbb{P}(\|X+Y\|_2\geq 1) \geq \frac{1}{2}\mathbb{P}(\|X\|_2\geq 1)^2\text{.} \end{equation*}
*Hint 1:*It might help to start with small dimensions, like \(n=1\) and \(n=2\text{,}\) to build some intuition.*Hint 2:*Choose \(X_1,X_2,\dots,X_n\) independently according to the same distribution as \(X\text{.}\) Take a limit of an appropriate quantity as \(n\to\infty\text{.}\)