## Section 4.7 Exercises

- Prove that, for \(k\geq2\text{,}\) if \(G\) is a graph with \(n\) vertices such that every vertex has degree greater than \(\left(\frac{k-2}{k-1}\right)n\text{,}\) then every edge of \(G\) is contained in a copy of \(K_k\text{.}\)
*Hint:*Induction with two base cases, \(k=2\) and \(k=3\text{.}\) - Let \(k,m\geq2\) be integers. The
*\(k\)-colour Ramsey number*of \(K_m\text{,}\) denoted by \(R_k(m)\text{,}\) is the minimum \(N\) such that, in every colouring of the edges of \(K_n\) with \(k\) colours, there is a monochromatic copy of \(K_m\text{.}\) Let \(r_k(m,n)\) denote the minimum number of monochromatic copies of \(K_m\) in a colouring of the edges of \(K_n\) with \(k\) colours. Prove that\begin{equation*} r_k(m,n)\geq \binom{n}{R_k(m)}\cdot \binom{n-m}{R_k(m)-m}^{-1} \end{equation*}for all \(n\geq1\text{.}\) - Prove that\begin{equation*} r_k(m,n)\leq \left(\frac{1}{k}\right)^{\binom{m}{2}-1}\binom{n}{m} \end{equation*}for all \(n\geq1\text{.}\)
- Prove that\begin{equation*} r_k(m,n)\leq (R_{k-1}(m)-1)\cdot\binom{\left\lceil n/(R_{k-1}(m)-1)\right\rceil}{m} \end{equation*}for all \(n\geq1\text{.}\)
- For the case \(k=m=3\text{,}\) which of the upper bounds on \(r_3(3;n)\) in the previous two parts of the question is better for large \(n\text{?}\)

- The goal of this exercise is to lead you through a proof of a lower bound on the sum of the number of triangles in \(G\) and the number of triangles in \(\overline{G}\text{.}\) This was proved by Goodman [136].
- Suppose that the edges of \(G\) are red and the edges of \(\overline{G}\) are blue. Argue that the sum \(\sum_{v\in V(G)}\binom{d_G(v)}{2}\) counts every triangle with three red edges exactly three times and every triangle with two red edges and one blue edge exactly once.
- Make a similar observation about the sum \(\sum_{v\in V(G)}\binom{d_{\overline{G}}(v)}{2}\text{.}\) You don’t have to justify it.
- Using question 3.a and question 3.b, prove that the number of triangles in \(G\) plus the number of triangles in \(\overline{G}\) is equal to\begin{equation*} \frac{1}{2}\left(\sum_{v\in V(G)}\binom{d_G(v)}{2} + \sum_{v\in V(G)}\binom{d_{\overline{G}}(v)}{2}-\binom{n}{3}\right)\text{.} \end{equation*}
- Optimize the equation from question 3.c over all choices of degrees to show that the number of triangles in \(G\) plus the number of triangles in \(\overline{G}\) is always at least\begin{equation*} \frac{1}{4}\left(\frac{n(n-1)(n-5)}{6}\right)=\frac{1}{4}\binom{n}{3} + O(n^2)\text{.} \end{equation*}

- Suppose that \(n\) is even and let \(G=K_{n/2,n/2}\text{.}\) What is the sum of the number of triangles in \(G\) and the number of triangles in \(\overline{G}\text{?}\)
- Suppose that \(G\) is a graph on \(n\) vertices such that each edge of \(K_n\) is included in \(G\) with probability \(1/2\text{,}\) independently of all of the other edges. What is the expected value of the sum of the number of triangles in \(G\) and the number of triangles in \(\overline{G}\text{?}\)

- Let \(n\geq1\) and \(1\leq m\leq \binom{n}{2}\text{.}\) Describe the graph \(G\) which has \(n\) vertices and \(m\) edges and, subject to this, the maximum number of triangles. Prove it is optimal.
*Hint:*Think about the collection of triangles as being a subset \(\mathcal{T}\) of \(\binom{[n]}{3}\text{.}\) One of the theorems in Chapter 2 may be helpful. - Show that, if \(n\) is even, the graph \(K_{n/2,n/2}\) is a tight example for the Goodman Bound in the case that \(p=1/2\text{.}\) That is, it has the right number of edges and that the number of triangles exactly matches the lower bound in the theorem.
- Show that, if \(n\) is divisible by \(3\text{,}\) then there exists a tight example for the Goodman Bound on \(n\) vertices with \(p=2/3\text{.}\)
- For each \(k\geq2\text{,}\) find a tight example for the Goodman Bound for the case \(p=1-\frac{1}{k}\text{.}\)

- The Erdős–Szekeres Theorem says that if \(r\) and \(s\) are integers and \(n\geq (r-1)(s-1)+1\text{,}\) then any sequence \(a_1,\dots,a_n\) of real numbers contains either an increasing sequence of length \(r\) or a decreasing sequence of length \(s\text{.}\) Prove that, for any \(r\geq2\) and \(\varepsilon>0\text{,}\) there exists \(n_0=n_0(r,\varepsilon)\) such that if \(n\geq n_0\text{,}\) then every sequence of \(n\) real numbers contains at least\begin{equation*} \left(\frac{((r-1)(r-2))!}{((r-1)^2+1)!}-\varepsilon\right)n^r \end{equation*}increasing or decreasing subsequences of length \(r\text{.}\)
- Let \(a_1,\dots,a_{k}\) be non-negative integers and define \(n=\sum_{i=1}^ka_i\text{.}\) Show that the number of edges in a complete \(k\)-partite graph with parts of size \(a_1,\dots,a_k\) is equal to\begin{equation*} \frac{1}{2}\left(n^2 - \sum_{i=1}^ka_i^2\right)\text{.} \end{equation*}
- Assuming (for simplicity) that \(r-1\) divides \(n\text{,}\) use question 8.a to prove that, if \(G\) is a complete \((r-1)\)-partite graph with parts of size \(a_1,\dots,a_{r-1}\) such that \(\sum_{i=1}^{r-1}a_i=n\text{,}\) then\begin{equation*} \ex(n,K_r) - |E(G)| = \frac{1}{2}\sum_{i=1}^{r-1}\left(a_i^2 -\left(\frac{n}{r-1}\right)^2\right)\text{.} \end{equation*}Also, prove that this sum can be rewritten as follows:\begin{equation*} \sum_{i=1}^{r-1}\left(a_i^2 -\left(\frac{n}{r-1}\right)^2\right) = \sum_{i=1}^{r-1}\left(a_i -\frac{n}{r-1}\right)^2\text{.} \end{equation*}
- Using question 8.b and Corollary C.0.6, prove that, if \(G\) is a complete \((r-1)\)-partite graph with \(n\) vertices such that \(|E(G)|\geq \ex(n,K_r)-t\text{,}\) then \(G\) can be transformed into a Turán graph by adding or removing at most \(n\sqrt{2t/(r-1)}\) edges.
- Using Theorem 4.5.1 and question 8.c, prove the following:
*For every \(r\geq3\) and \(\varepsilon>0\) there exists \(\delta=\delta(r,\varepsilon)>0\) and \(n_0=n_0(r,\varepsilon)\) such that if \(G\) is a \(K_r\)-free graph with \(n\geq n_0\) vertices and at least*\begin{equation*} \ex(n,K_r) - \delta n^2 \end{equation*}edges, then \(G\) can be transformed into a Turán graph by adding and removing at most \(\varepsilon n^2\) edges.

- Given \(\mathcal{F}\subseteq 2^{[n]}\text{,}\) say that a set \(A\subseteq [n]\) is
*\(\mathcal{F}\)-free*if there does not exist \(B\in\mathcal{F}\) such that \(B\subseteq A\text{.}\)- Show that \(\{A\subseteq [n]: A\text{ is -free} \}\) is a downset.
- Let \(\ex_\mathcal{F}(n)\) be the largest cardinality of a set \(A\subseteq [n]\) that is \(\mathcal{F}\)-free. Show that, for any \(X\subseteq[n]\text{,}\)\begin{equation*} |\{B\in\mathcal{F}: B\subseteq X\}|\geq |X| - \ex_\mathcal{F}(n)\text{.} \end{equation*}
- Suppose that \(\mathcal{F}\subseteq \binom{[n]}{k}\) for some \(k\geq1\text{.}\) Show that, for any \(X\subseteq[n]\) such that \(|X|\geq 2\ex_\mathcal{F}(n)\text{,}\)\begin{equation*} |\{B\in\mathcal{F}: B\subseteq X\}|\geq \left(\frac{|X|}{2 \ex_\mathcal{F}(n)}\right)^k\cdot \ex_\mathcal{F}(n)\text{.} \end{equation*}
*Hint:*Linearity of expectation might help.

- Given graphs \(H_1\) and \(H_2\text{,}\) let \(H_1\sqcup H_2\) denote the disjoint union of \(H_1\) and \(H_2\text{.}\) Prove that, for any graphs \(H_1,H_2\) and \(G\text{,}\)\begin{equation*} t(H_1\sqcup H_2,G)=t(H_1,G)t(H_2,G)\text{.} \end{equation*}
- Given graphs \(G_1\) and \(G_2\text{,}\) let \(G_1 \times G_2\) be the graph with vertex set \(V(G_1)\times V(G_2)\) and edge set\begin{equation*} \{(u,v)(w,x): uw\in E(G_1)\text{ and } vx\in E(G_2)\}\text{.} \end{equation*}The graph \(G_1\times G_2\) is called the
*tensor*or*categorical product*of \(G_1\) and \(G_2\) (among other names). Prove that, for any graphs \(H,G_1\) and \(G_2\text{,}\)\begin{equation*} t(H,G_1\times G_2)=t(H,G_1)t(H,G_2)\text{.} \end{equation*} - By imitating the proof of Theorem 4.2.7, prove that \(t(K_{4,4},G)\geq t(C_4,G)^{4}\) for any graph \(G\text{.}\) Also, for fixed \(p\in (0,1)\text{,}\) provide an example to show that this is asymptotically tight for graphs \(G\) with \(t(C_4,G)=p^4\text{.}\)
- Let \(n\) be an even natural number and let \(G\) be a subgraph of \(K_{n/2,n/2}\) with \(|V(G)|=n\text{.}\) Prove that\begin{equation*} t(C_4,G) \geq 2\cdot t(P_3,G)^2\text{.} \end{equation*}
*Hint:*Follow the proof of Theorem 4.12 after equation (4.13). - Prove that, for every \(s,t\geq1\text{,}\)\begin{equation*} t(K_{s,t},G)\geq t(K_2,G)^{st}\text{.} \end{equation*}
*Hint:*Use Corollary C.0.5 twice. - Let \(B\) be the 5-vertex “bowtie” graph obtained by gluing two triangles together on a vertex. Prove that \(t(B,G)\geq t(K_3,G)^2\) for any graph \(G\text{.}\)
- Let \(K_4^-\) be the graph obtained from \(K_4\) by deleting one edge. Prove that \(t(K_4^-,G)t(K_2,G)\geq t(K_3,G)^2\) for every graph \(G\text{.}\)
- Prove that \(t(P_5,G)\geq t(K_2,G)^4\) for every graph \(G\text{.}\) Generalize the proof to yield \(t(P_{2^k+1},G)\geq t(K_{2},G)^{2^k}\) for any \(k\geq1\text{.}\) }
- A
*edge coloured graph*is a tuple \(\vec{H}:=(H_1,\dots,H_k)\) where \(H_1,\dots,H_k\) are graphs with the same vertex set; i.e. \(V(H_i)=V(H_j)\) for all \(1\leq i,j\leq k\text{.}\) We let \(V(\vec{H})\) denote \(V(H_i)\) for any \(i\text{.}\) You can visualize a \(k\)-edge coloured graph as being \(k\) graphs \(H_1,\dots,H_k\) drawn on top of each other, where the edges of \(H_i\) are in colour \(i\text{.}\) If \(\vec{H}\) and \(\vec{G}\) are \(k\)-edge coloured graphs, then \(f:V(\vec{H})\to V(\vec{G})\) is a*homomorphism*if, for any \(1\leq i\leq k\) and \(uv\in E(H_i)\text{,}\) it holds that \(f(u)f(v)\in E(G_i)\text{.}\) Define \(\hom(\vec{H},\vec{G})\) and \(t(\vec{H},\vec{G})\) analogously to the case of graphs.- Let \(\vec{H}:=(H_1,\dots,H_k)\) be a \(k\)-edge coloured graph, let \(H\) be a graph with vertex set \(V(\vec{H})\) and edge set \(\bigcup_{i=1}^kE(H_i)\) and let \(G\) be any graph. Let \(\vec{G}\) be the \(k\)-edge coloured graph \((G_1,\dots,G_k)\) where \(G_1=G_2=\cdots =G_k=G\text{.}\) Prove that \(t(\vec{H},\vec{G})=t(H,G)\text{.}\)
- Let \(\vec{C_4}=(H_1,H_2,H_3,H_4)\) be the \(4\)-edge coloured graph on vertex set \(\{1,2,3,4\}\) where, for \(1\leq i\leq 4\text{,}\) the graph \(H_i\) contains only the edge \(i(i+1)\) where we view the vertices modulo \(4\) (i.e. \(5\equiv 1\)). Prove that, for any \(4\)-coloured graph \(\vec{G}\text{,}\)\begin{equation*} t(\vec{C_4},\vec{G})^2 \leq t((H_1,H_2,H_3,H_4),(G_1,G_1,G_3,G_3))t((H_1,H_2,H_3,H_4),(G_2,G_2,G_4,G_4))\text{.} \end{equation*}
- Prove that, for any \(4\)-coloured graph \(\vec{G}\text{,}\)\begin{equation*} t(\vec{C_4},\vec{G})^4\leq t(C_4,G_1)t(C_4,G_2)t(C_4,G_3)t(C_4,G_4)\text{.} \end{equation*}(Hint: The previous two parts of the question are useful).
- Let \(H\) be a graph with \(k\) edges and let \(\vec{H}=(H_1,\dots,H_k)\) be a \(k\)-edge coloured graph with vertex set \(V(H)\) where each edge of \(H\) belongs to exacty one of the graphs \(H_1,\dots,H_k\text{.}\) Suppose that\begin{equation*} t(\vec{H},\vec{G})^k\leq \prod_{i=1}^kt(H,G_i) \end{equation*}for any \(k\)-edge coloured graph \(\vec{G}=(G_1,\dots,G_k)\text{.}\) Prove that\begin{equation*} t(H,G)\geq t(K_2,G)^{|E(H)|} \end{equation*}for every graph \(H\text{.}\) (Hint: Let \(G_1=G\) and let \(G_2,\dots,G_k\) be appropriately chosen random graphs).
- Deduce Theorem 4.2.7 from the previous parts of this question.

- Let \(\lambda_1,\dots,\lambda_n\) be the eigenvalues of the adjacency matrix of a graph \(G\) on \(n\) vertices. Prove that \(\sum_{i=1}^n\lambda_i^2=2|E(G)|\text{.}\)
- Prove that every graph \(G\) satisfies\begin{equation*} t(C_{24},G)\leq t(C_{42},G)^{2/5}t(C_{12},G)^{3/5}\text{.} \end{equation*}
- Describe a sequence \(G_1,G_2,\dots\) of graph such that \(\lim_{n\to \infty}t(K_2,G_n)=1/2\) and\begin{equation*} \lim_{n\to\infty} \left(t(C_{24},G_n)- t(C_{42},G_n)^{2/5}t(C_{12},G_n)^{3/5}\right)=0\text{.} \end{equation*}It is enough to describe a correct construction; you do not need to rigorously prove that it is correct.

- Let \(\varepsilon_0,\delta_0>0\) and suppose that \(G\) is a graph such that\begin{equation*} t(C_4,G)\leq t(K_2,G)^4+\varepsilon_0^4 \end{equation*}and\begin{equation*} t(C_6,G)\leq t(K_2,G)^6+\delta_0^6\text{.} \end{equation*}Prove that\begin{equation*} t(C_5,G)\geq t(K_2,G)^5-\varepsilon_0^2\delta_0^3\text{.} \end{equation*}
- Let \(G\) be a graph with \(n\) vertices and let \(\lambda_1,\dots,\lambda_n\) be the eigenvalues of its adjacency matrix indexed so that \(\lambda_1\geq\cdots \geq\lambda_n\text{.}\) Prove that \(G\) is bipartite if and only if its spectrum is
*symmetric*; i.e., for every \(1\leq i\leq n\text{,}\)\begin{equation*} \lambda_i = -\lambda_{n-i+1}\text{.} \end{equation*}Conclude that, if \(G\) is a bipartite graph on an odd number of vertices, then the adjacency matrix of \(G\) is singular. - Let \(G\) be a graph with \(n\) vertices and let \(\lambda_1,\dots,\lambda_n\) be the eigenvalues of its adjacency matrix indexed so that \(\lambda_1\geq\cdots \geq\lambda_n\text{.}\) Given \(S\subseteq V(G)\text{,}\) let \(\overline{S}=V(G)\setminus S\text{.}\)
- Prove that, for every set \(S\subseteq V(G)\) and \(\alpha,\beta>0\text{,}\)\begin{equation*} \lambda_n \leq \frac{2\alpha^2e(S) +2\beta^2e(\overline{S}) -2\alpha\beta e(S,\overline{S}) }{\alpha^2 |S| +\beta^2|\overline{S}|}\text{.} \end{equation*}
*Hint:*Choose an appropriate vector \(\vec{v}\) and apply Lemma 4.3.3 part b to the matrix \(-A_G\text{.}\) - Let \(\varepsilon>0\text{.}\) Suppose that \(G\) is a graph with \(n\) vertices and that \(S\subseteq V(G)\) such that \(|S|=n/2\) and\begin{equation*} e(S,\overline{S})\geq \frac{|E(G)|}{2} + \frac{\varepsilon n^2}{4}\text{.} \end{equation*}Prove that\begin{equation*} t(C_4,G)\geq t(K_2,G)^4 + \varepsilon^4\text{.} \end{equation*}

- The characteristic polynomial of the adjacency matrix of \(G\) is \(p_{G}(x):=\prod_{i=1}^n(x-\lambda_i)\) where \(\lambda_1,\dots,\lambda_n\) are the eigenvalues of \(A_G\text{.}\) Prove that the following holds for all \(x>\max\{\lambda_1,\dots,\lambda_n\}\text{:}\)\begin{equation*} \ln(p_G(x)) = n\ln(x) - \sum_{r=2}^\infty\frac{\hom(C_r,G)}{rx^r} \end{equation*}where \(C_2=K_2\text{.}\)
*Hint:*The Taylor expansion of \(\ln(1-z\lambda)\) at \(z=0\) may be helpful. - Given a \(k\)-uniform hypergraph \(H\text{,}\) define \(\pi(H):=\lim_{n\to\infty}\frac{\ex(n,H)}{\binom{n}{k}}\) where \(\ex(n,H)\) is the maximum number of hyperedges in a \(k\)-uniform hypergraph on \(n\) vertices without a copy of \(H\text{.}\) State and prove a version of Theorem 4.4.1 for hypergraphs with this definition of \(\pi(H)\text{.}\)
- Derive the Erdős–Stone Theorem from Exercise 36.b in Section 3.6, Turán’s Theorem and the Erdős–Simonovits Supersaturation Theorem.
- Prove Lemma 4.6.3.
- Prove that there exist \(\varepsilon>0\text{,}\) \(\alpha>0\) and \(n_0\in \mathbb{N}\) such that, if \(n\geq n_0\text{,}\) then every graph \(G\) with \(n\) vertices and at least \(2n^{2.1}\) triangles contains a subgraph \(G'\) with at least \(n^\varepsilon\) vertices and at least \(|V(G')|^{2.1}\) triangles in which every vertex is contained in at most \(\alpha t(G')/|V(G')|\) triangles where \(t(G')\) is the number of triangles in \(G'\text{.}\)
- For each \(m\geq1\text{,}\) let \(F_m\) be the graph obtained from \(K_{m,m}\) by deleting \(m\) disjoint edges (i.e. a matching of cardinality \(m\)). Note that \(F_3=C_6\) and \(F_4=Q_3\text{.}\) For each \(m\geq5\text{,}\) prove that \(\ex(n,F_m)=O\left(n^{2-\alpha_m}\right)\) for the largest value of \(\alpha_m\) that you can. You will get full marks for a correct proof of the same value of \(\alpha_m\) that the lecturer gets in their solution; bonus marks for doing better. You can feel free to be “relaxed” about constant factors.
- For each \(d,\delta\in(0,1)\text{,}\) show that there exists \(\varepsilon=\varepsilon(d,\delta)\) such that if \(G\) is a graph with \(n\) vertices such that every set \(A\subseteq V(G)\) with \(|A|\geq \delta n\) has at least \(d|A|^2/2\) edges, then \(t(K_3,G)\geq (1-\varepsilon)d\cdot t(K_2,G)^2\text{.}\)