Let \(0\lt \varepsilon\lt 1\text{,}\) let \(G\) be a graph. Suppose that \((X_1,X_2)\) is a partition of \(V(G)\) such that the pair \((X_1,X_2)\) is \(\varepsilon\)-regular in \(G\text{.}\) Show that \((X_1,X_2)\) is \(\varepsilon\)-regular in the complement \(\overline{G}\) of \(G\text{.}\)
Prove that if \(G\) is a graph with \(n\) vertices and at most \(\varepsilon^3\left\lfloor\frac{n^2}{4}\right\rfloor\) edges, then \(G\) has an \(\varepsilon\)-regular partition with exactly two parts.
Let \(G\) be a graph and \((X_1,X_2,X_3)\) be a partition of \(V(G)\text{.}\) Suppose that
for all distinct \(i,j\in \{1,2,3\}\) and that all of the pairs \((X_i,X_j)\) are \(\varepsilon\)-regular. Let \(P_3\) be the path on three vertices and, for \(i\in\{1,2,3\}\text{,}\) let \(v_i\) be the \(i\)th vertex on the path. Show that the number of induced copies of \(P_3\) in which \(v_i\) is in \(X_i\) for \(1\leq i\leq 3\) is at least
State and prove a version of Lemma 5.1.7 for counting copies of \(K_4\text{,}\) where \(V(G)\) is partitioned into four sets \(X_1,X_2,X_3\) and \(X_4\text{.}\)
Consider the following version of the Triangle Removal Lemma for deleting vertices instead of edges: For every \(0\lt \delta\lt 1\) there exists \(0\lt \gamma\lt 1/6\) such that if \(G\) is a graph with \(n\) vertices and at most \(\gamma n^3\) triangles, then \(G\) can be made triangle-free by deleting at most \(\delta n\) vertices. Disprove this statement.
The goal of this exercise is to disprove a natural generalization of the Counting Lemma (Lemma 5.1.7) for \(3\)-uniform hypergraphs. 1
Note that there is a different generalization of the counting lemma for hypergraphs that is true.
Let \(n\) be divisible by \(4\) and let \(V=V_1\sqcup V_2\sqcup V_3\sqcup V_4\) where \(|V_i|=n/4\) for \(1\leq i\leq 4\text{.}\)
Let \(H\) be a \(3\)-uniform hypergraph with \(V(H)=V\) such that, for distinct \(i,j,k\text{,}\) if \((x,y,z)\in V_i\times V_j\times V_k\text{,}\) then \(E(H)\) contains \(\{x,y,z\}\) with probability \(1/8\) independently of all other triples. Compute the expected number of sets \(S\subseteq V(G)\) such that \(|S|=4\) and \(\binom{S}{3}\subseteq E(H)\text{.}\)
Let \(G\) be a graph with vertex set \(V(G)=V\) where, if \(u\in V_i\) and \(v\in V_j\) with \(i\neq j\text{,}\) then \(uv\) is in \(E(G)\) with probability \(1/2\) independently of any other pair. Let \(H'\) be a hypergraph with vertex set \(V\) where \(\{x,y,z\}\in E(H')\) if \(x,y\) and \(z\) form a triangle in \(G\text{.}\) For distinct \(i,j,k\) and \((x,y,z)\in V_i\times V_j\times V_k\text{,}\) determine the probability that \(\{x,y,z\}\in E(H')\text{.}\)
Let \(H'\) be the hypergraph as in the previous part of the question. Compute the expected number of sets \(S\subseteq V(G)\) such that \(|S|=4\) and \(\binom{S}{3}\subseteq E(H')\text{.}\)
Write a natural generalization of Lemma 5.1.7 and explain why the hypergraphs \(H\) and \(H'\) disprove that statement. In your explanation, you can make some reasonable probabilistic assumptions without proving them.
Let \(r_k(n)\) be the cardinality of the largest subset of \([n]\) without a k-term arithmetic progression. Prove that, for any \(M\leq n\text{,}\)
Let \(n\) and \(m\) be integers such that \(3\binom{m}{2} + m \lt n\text{.}\) Show that if \(A\subseteq [n]\) such that \(|A|=m\) and \(A\) does not contain a non-trivial \(3\)-term arithmetic progression, then there exits \(x\in [n]\setminus A\) such that \(A\cup\{x\}\) does not contain a non-trivial \(3\)-term arithmetic progression.
For every \(1\leq k\leq n\text{,}\) find a simple formula for the number of non-trivial \(k\)-term arithmetic progressions in \([n]\) (i.e. not in terms of a summation).
Our goal in this exercise is to prove the following. Behrend’s Theorem:There exists \(c>0\) such that, for all \(n\geq1\text{,}\) there is a set \(A\subseteq [n]\) with \(|A|\geq n\exp(-c\sqrt{\log(n)})\) containing no \(3\)-term arithmetic progression.
Let \(M\) and \(\ell\) be integers and, for each \(r\in\mathbb{N}\text{,}\) define
There does not exist \((x_1,\dots,x_\ell), (y_1,\dots,
y_\ell),(z_1,\dots,z_\ell)\in S_r\) such that \((y_1,\dots,y_\ell) - (x_1,\dots,x_\ell) =(z_1,\dots,z_\ell) - (y_1,\dots,y_\ell)\text{.}\)
There exists some \(r\) such that \(|S_r|\geq M^{\ell-2}/\ell\text{.}\)
for each \((x_1,\dots,x_\ell)\in S_r\text{.}\) Prove that
\(\pi\) is injective,
if \((x_1,\dots,x_\ell), (y_1,\dots,
y_\ell),(z_1,\dots,z_\ell)\in [M]^\ell\) such that \(\pi(y_1,\dots,y_\ell) - \pi(x_1,\dots,x_\ell) = \pi(z_1,\dots,z_\ell) - \pi(y_1,\dots,y_\ell)\text{,}\) then \((y_1,\dots,y_\ell) - (x_1,\dots,x_\ell) =(z_1,\dots,z_\ell) - (y_1,\dots,y_\ell)\text{.}\)
\(\pi(x_1,\dots,x_\ell)\leq (2M)^\ell\) for all \((x_1,\dots,x_\ell)\in [M]^\ell\text{.}\)
Let \(\ell=\lfloor\sqrt{\log(n)}\rfloor\) and \(M=\lfloor n^{1/\ell}/2\rfloor\) and choose \(r\) and define \(A=\pi(S_r)\) where \(r\) is chosen so that \(|S_r|\) is maximum. Show that
\(A\) has no \(3\)-term arithmetic progression.
\(|A|\geq n\exp(-c\sqrt{\log(n)})\) for some \(c>0\text{.}\)
Prove that there exists \(c>0\) such that, for all \(n\geq1\text{,}\) there is a set \(A\subseteq [n]\) with \(|A|\geq n\exp(-c\sqrt{\log(n)})\) such that there does not exist \(x,y,z,w\in A\) which are not all equal such that \(x+y+z=3w\text{.}\)Hint: Adapt the approach in Exercise 10 from this section.
Consider the following extension of the Triangle Removal Lemma to \(r\)-uniform hypergraphs: Hypergraph Removal Lemma:Let \(r\geq2\text{.}\) For every \(0\lt \delta\lt \frac{1}{r!}\) there exists \(\gamma=\gamma(\delta)\) with \(0\lt \gamma\lt \frac{1}{(r+1)!}\) such that if \(H\) is an \(r\)-uniform hypergraph with at most \(\gamma n^{r+1}\) copies of \(K_{r+1}^{(r)}\text{,}\) then \(H\) can be made \(K_{r+1}^{(r)}\)-free by deleting at most \(\delta n^r\) hyperedges.
Use the Hypergraph Removal Lemma to prove the following extension of the Ruzsa–Szemerédi Theorem: Let \(r\geq2\text{.}\) For every \(\varepsilon>0\) and \(\ell\geq1\) there exists \(n_0=n_0(r,\varepsilon,\ell)\) such that if \(H\) is an \(r\)-uniform hypergraph such that every hyperedge of \(H\) is contained in at most \(\ell\) copies of \(K_{r+1}^{(r)}\text{,}\) then the number of copies of \(K_{r+1}^{(r)}\) in \(G\) is at most \(\varepsilon n^r\text{.}\)
Use the extension of the Ruzsa–Szemerédi Theorem from question 12.a to prove the following: Szemerédi’s Theorem:For every \(k\geq3\) and \(\delta>0\) there exists \(N_0(k,\delta)\) such that if \(n\geq N_0(k,\delta)\text{,}\) then every set \(A\subseteq [n]\) with \(|A|\geq \delta n\) contains a non-trivial \(k\)-term arithmetic progression.
for \(x,y,z\in \mathbb{N}\text{.}\) A set \(A\subseteq\mathbb{N}\times\mathbb{N}\) is corner-free if it does not contain a corner as a subset. Use the extension of the Ruzsa–Szemerédi Theorem from question 12.a to prove the following: Corners Theorem:For every \(\delta>0\) there exists \(N_0(\delta)\) such that if \(n\geq N_0(\delta)\text{,}\) then every corner-free subset of \([n]\times [n]\) has cardinality at most \(\delta n^2\text{.}\)
Show that the Corners Theorem (see Exercise 12.c in this section) implies Roth’s Theorem. Hint: Prove the contrapositive.
Prove that, for every \(\varepsilon>0\text{,}\) there exists \(n_0=n_0(\varepsilon)\) such that if \(G\) is a graph on \(n\geq n_0\) vertices in which every edge is contained in exactly one triangle, then \(|E(G)|\leq \varepsilon n^2\text{.}\)
Let \(G\) be a graph. A set \(M\subseteq E(G)\) is called an matching if the edges in \(M\) are pairwise disjoint. We say that \(M\) is an induced matching if it is a matching and, additionally, for any distinct \(e_1,e_2\in M\) there are no edges of \(G\) linking an endpoint of \(e_1\) to an endpoint of \(e_2\text{.}\) Prove the following: For every \(\varepsilon>0\) there exists \(n_0=n_0(\varepsilon)\) such that if \(G\) is a bipartite graph with \(n\geq n_0\) vertices and \(E(G)=M_1\cup\cdots M_n\) where the sets \(M_1,\dots,M_n\) are disjoint induced matchings in \(G\text{,}\) then \(|E(G)|\leq \varepsilon n^2\text{.}\)Hint: Use Corollary 5.2.4 with \(\ell=1\text{.}\)
Let \(G\) be a graph with \(n\) vertices, where \(n\) is divisible by \(3\text{,}\) such that every edge of \(G\) is contained in exactly one triangle. Using a probabilistic argument, or otherwise, show that there is a bipartite subgraph \(G'\) of \(G\) with \(2n/3\) vertices and at least \(\frac{2|E(G)|}{27}\) edges such that the edges of \(G'\) can be partitioned into \(n/3\) disjoint induced matchings.
Using the Regularity Lemma, prove that the number of \(n\)-vertex triangle-free graphs is between \(2^{\lfloor n^2/4\rfloor}\) and \(2^{(1/4+o(1))n^2}\text{.}\)Hint 1: You may want to use that \(\binom{N}{K}\leq \left(\frac{eN}{K}\right)^K\) holds for any \(N\geq K\geq 1\text{.}\)Hint 2: Count triangle-free graphs with a specific regularity partition and multiply by the number of partitions.
Using the Regularity Lemma (Theorem 5.2.1), prove that one can instead obtain a partition into \(k\) parts \(X_1,\dots,X_k\) (the value of \(k\) might be different) such that for every \(1\leq i\leq k\) there are at most \(\varepsilon k\) indices \(j\neq i\) such that \((X_i,X_j)\) is not \(\varepsilon\)-regular. Hint: Apply the Regularity Lemma for some \(\varepsilon'\lt \varepsilon\) of your choosing to get a partitioning \(X_1',\dots,X_{k'}'\text{.}\) How many of the parts \(X_i'\) can be involved in more than \(\varepsilon k'\) pairs which are not \(\varepsilon\)-regular? What happens if we incorporate the vertices of these parts into the other parts?
Prove that, for every \(\varepsilon>0\) and \(t\in \mathbb{N}\text{,}\) there exists \(k_0(\varepsilon,t)\) such that, for every graph \(G\text{,}\) there is a partition \(X_0,X_1,\dots,X_k\) of \(V(G)\) and a spanning 2
A spanning subgraph of \(G\) is a subgraph \(G'\) of \(G\) such that \(V(G')=V(G)\text{.}\)
subgraph \(G'\) of \(G\) such that
\(|X_0|\leq \varepsilon|V(G)|\text{,}\)
\(|X_1|=|X_2|=\cdots=|X_k|\text{,}\)
\(G'\) contains no edges within \(X_i\) for any \(0\leq i\leq k\text{,}\)
the density between \(X_i\) and \(X_j\) in \(G'\) is either \(0\) or at least \(10\varepsilon\text{,}\)
\((X_i,X_j)\) is \(\varepsilon\)-regular in \(G'\) for all \(1\leq i\neq j\leq k\text{,}\) and
Let \(H\) be a graph. An \(H\)-tiling of a graph \(G\) is a collection \(\mathcal{H}\) of disjoint subsets of \(V(G)\) such that every set in \(\mathcal{H}\) contains a copy of \(H\text{.}\) Say that an \(H\)-tiling \(\mathcal{H}\)covers a vertex \(v\in V(G)\) if there exists a set in \(\mathcal{H}\) containing \(v\text{.}\) If \(\mathcal{H}\) does not cover \(v\text{,}\) say that it misses\(v\text{.}\)
Let \(K_{a,b,c}\) be the complete tripartite graph with parts of sizes \(a,b\) and \(c\text{.}\) Assume that \(a\leq b\leq c\text{.}\) Show that, for all \(\gamma>0\text{,}\) there exists a graph \(G\) such that \(\delta(G) \geq \left(\frac{2a+b+c}{2(a+b+c)}-\gamma\right)|V(G)|\) and every \(K_{a,b,c}\)-tiling of \(G\) misses at least \(\gamma\left(\frac{1}{b+c}+\frac{1}{a}\right)|V(G)|\) vertices of \(G\text{.}\)
Given a graph \(H\text{,}\) let \(\sigma(H)\) be the minimum of \(\left|f^{-1}(\{1\})\right|\) over all proper colourings \(f:V(H)\to \{1,\dots, \chi(H)\}\) of \(H\text{.}\) Generalize the construction in question 20 to find a functions \(\phi(H)\) and \(\tau(H)\text{,}\) depending on \(\sigma(H)\text{,}\)\(\chi(H)\) and \(|V(H)|\text{,}\) such that for all \(\gamma>0\text{,}\) there exists a graph \(G\) such that \(\delta(G)\geq \left(\phi(H)-\gamma\right)|V(G)|\) such that every \(H\)-tiling of \(G\) misses at least \(\gamma\tau(H)|V(G)|\) vertices of \(G\text{.}\) Make \(\phi(H)\) as large as you can.
Prove that, for every \(\varepsilon>0\text{,}\) there exists \(\delta=\delta(\varepsilon)>0\) such that if \(G\) is an \(n\)-vertex bipartite graph with bipartition \((A,B)\) with \(||A|-|B||\lt \varepsilon n\text{,}\) the pair \((A,B)\) is \(\varepsilon\)-regular and \(d(A,B)>10\varepsilon\text{,}\) then \(G\) contains a matching \(M\) of size at least \(\left(\frac{1}{2}-\delta\right)n\text{.}\)Hint: Hall’s Theorem for matchings in bipartite graphs. If you don’t know it, look it up!
Our goal is to prove the following theorem of Thomassen [285]: Thomassen’s Theorem.For every \(\delta>0\) there exists \(C=C(\delta)\) such that, if \(G\) is a triangle-free graph with \(n\) vertices and minimum degree at least \(\left(\frac{1}{3}+\delta\right)n\text{,}\) then \(\chi(G)\leq C\text{.}\) Let \(0\lt \delta\lt 1/2\) and let \(G\) be a graph satisfying the hypotheses of Thomassen’s Theorem. Define \(\varepsilon:=\frac{\delta}{1000}\text{,}\)\(t=\lceil 1000/\delta\rceil\) and let \(X_1,\dots,X_k\) be a partition of \(V(G)\) obtained from applying the Regularity Lemma to \(G,\varepsilon\) and \(t\text{.}\) Let \(d=50\varepsilon\) and, for \(I\subseteq [k]\text{,}\) let
Note that the sets \(X_I\) for \(I\subseteq [k]\) partition \(V(G)\text{.}\) In all of the following questions, you may assume that \(\delta n>10^{100}k\text{.}\)
Prove that, if \(|I|\leq 2k/3\text{,}\) then \(X_I\) is an independent set.
Prove that, if \(|I|\geq 2k/3\text{,}\) then \(X_I=\emptyset\text{.}\)
Deduce Thomassen’s Theorem.
The goal in this question is to show that Thomassen’s Theorem from Exercise 22 in this section is asymptotically tight. Prove that there exists a sequence \(G_1,G_2,G_3,\dots\) of graphs such that
\(G_n\) is triangle-free for all \(n\geq1\text{,}\)
\(\lim_{n\to\infty}\frac{\delta(G_n)}{|V(G_n)|}= \frac{1}{3}\) where \(\delta(G_n)\) is the minimum degree of \(G_n\text{,}\) and
\(\lim_{n\to\infty}\chi(G_n)=\infty\text{.}\)
Hint: Look up the Mycielski construction and apply it. You may need to solve some recurrence relations.
