Exercises

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{.}\)
1. 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{.}\)
2. 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{.}\)
3. 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{.}\)
4. 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].
1. 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.
2. 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.
3. 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*}
4. 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*}
1. 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{?}\)
2. 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{?}\)
1. Given a graph \(G\) and \(u,v\in V(G)\text{,}\) let \(1_{\{uv\in E(G)\}}\) be equal to \(1\) if \(uv\in E(G)\) and \(0\) otherwise. Observe that
  
  \begin{equation*} \hom(K_3,G) = \sum_{u,v\in V(G)}1_{\{uv\in E(G)\}} \cdot |N(u)\cap N(v)|. \end{equation*}
  
  Use this to prove that
  
  \begin{equation*} t(K_3,G)^2\leq t(K_2,G)t(C_4,G). \end{equation*}
  
  Explain why this implies that
  
  \begin{equation*} t(K_3,G)\leq t(K_2,G)^{3/2}. \end{equation*}
2. For each \(0\leq t\leq n\text{,}\) describe an example of a graph \(G\) on \(n\) vertices with \(\hom(K_2,G)=t(t-1)\) and \(\hom(K_3,G)=t(t-1)(t-2)\text{.}\) Using this, explain why the last inequality in the previous part of the question is asymptotically tight.
3. Prove that, for any \(k\geq 3\) and any graph \(G\text{,}\)
  
  \begin{equation*} t(K_k,G)\leq t(K_{k-1},G)^{\frac{k}{k-1}}. \end{equation*}
  
  Hint: Holder’s Inequality.
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.
1. Let \(2\leq m\leq n\) and suppose that \(G\) is an \(n\)-vertex graph with \(\hom(K_3,G)\geq m(m-1)(m-2)\text{.}\) Prove that
  
  \begin{equation*} \hom(P_3,G)\geq m(m-1)^2. \end{equation*}
  
  Also, prove that this bound is tight for all \(2\leq m\leq n\text{.}\) Hint: Theorem 2.3.24 may help.
2. Generalize the result in the previous part of the question to bounding \(\hom(K_{1,k-1})\) from below in a graph \(G\) with \(\hom(K_k,G)\geq k!\binom{m}{k}\) and prove this generalization.
1. 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.
2. 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{.}\)
3. 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{.}\)
1. 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*}
2. Assuming (for simplicity) that \(r-1\) divides \(n\text{,}\) use question 10.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*}
3. Using question 10.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.
4. Using Theorem 4.5.1 and question 10.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{.}\)
1. Show that \(\{A\subseteq [n]: A\text{ is -free} \}\) is a downset.
2. 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*}
3. 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.
1. 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{.}\)
2. 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*}
3. 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).
4. 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).
5. 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{.}\)
1. 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*}
  
  Hint: Apply Corollary 4.3.6 and Lemma C.0.4.
2. 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*}

Hint: Apply Corollary 4.3.6 and Lemma C.0.4.
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{.}\)
1. 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{.}\)
2. 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 1: The Taylor expansion of \(\ln(1-z\lambda)\) at \(z=0\) may be helpful. Hint 2: Look up the Perron-Frobenius Theorem. You may need it.
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 instructor gets in their solution; bonus marks for doing better, provided that the proof is correct. You can feel free to be “relaxed” about the constant factor in the Big-O notation. You are allowed to use any theorem stated in the first four chapters of the notes without proof.
1. Recall that \(Q_d\) is the \(d\)-dimensional hypercube graph. For \(d\geq1\) let \(Q_{d+1/2}\) to be the graph obtained from taking two disjoint copies of \(Q_d\) and gluing them together on a copy of \(Q_{d-1}\text{.}\) For example, \(Q_{1+1/2}\) is a path on three vertices and \(Q_{2+1/2}\) is a grid graph of height one and width two. Prove that
  
  \begin{equation*} \hom(Q_{d+1/2},G)\hom(Q_{d-1},G)\geq \hom(Q_d,G)^2 \end{equation*}
  
  for every graph \(G\) and \(d\geq 1\text{.}\)
2. Prove that
  
  \begin{equation*} \hom(Q_{d+1},G)\hom(Q_{d-1},G)^2\geq \hom(Q_{d+1/2},G)^2 \end{equation*}
  
  for every graph \(G\) and \(d\geq 1\text{.}\)
3. Prove that
  
  \begin{equation*} \hom(Q_{d},G)\geq t(K_2,G)^{d2^{d-1}} \end{equation*}
  
  for every graph \(G\) and \(d\geq 1\text{.}\)
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{.}\)

Prev Top Next