Extremal results for sparse pseudorandom graphs

by Yufei Zhao

David Conlon, Jacob Fox and I have just uploaded to the arXiv our paper Extremal results in sparse pseudorandom graphs. The main advance of this paper is a sparse extension of the counting lemma associated to Szemerédi’s regularity lemma, allowing us to extend a wide range of classical extremal and Ramsey results to sparse pseudorandom graphs.

An important trend in modern combinatorics research is in extending classical results to the sparse setting. For instance, Szemerédi’s theorem says that every subset of the integers with positive density contains arbitrarily long arithmetic progressions. The celebrated result of Green and Tao says that the primes also contain arbitrarily long arithmetic progressions. While the primes have zero density in the integers, they may be placed inside a pseudorandom set of “almost primes” with positive relative density. Green and Tao established a transference principle, allowing them to apply Szemerédi’s theorem as a black box to the sparse setting. Our work has a similar theme. We establish a transference principle extending many classical extremal graph theoretic results to sparse pseudorandom graphs.

One of the most powerful tools in extremal graph theory is Szemerédi’s regularity lemma. Roughly speaking, it says that every large graph can be partitioned into a bounded number of roughly equally-sized parts so that the graph is random-like between pairs of parts. With this tool in hand, many important results in extremal graph theory can be proven using a three-step recipe, known as the regularity method:

  1. Starting with any graph {G}, apply Szemerédi’s regularity lemma to obtain a regular partition;
  2. Clean up the graph and create an associated reduced graph. Solve an easier problem in the reduced graph;
  3. Apply the counting lemma. Profit.

The counting lemma is a result that says that the number of embeddings of a fixed graph (e.g., a triangle) into the regular partition is roughly what you would expect if the large graph were actually random. The original version of Szemerédi’s regularity lemma is useful only for dense graphs. Kohayakawa and Rödl later independently developed regularity lemmas for sparse graphs. However, for sparse extensions of the applications, the counting lemma remained a key missing ingredient and an important open problem in the field. Our main advance lies in a counting lemma that complements the sparse regularity lemma.

In order to state our results, we need to explain what we mean by a pseudorandom graph. We say that a graph {\Gamma} is {(p, \beta)}jumbled if for all vertex subsets {X} and {Y} of {\Gamma}, we have

\displaystyle \left| e(X,Y) - p \left| X \right| \left| Y \right| \right| \leq \beta \sqrt{\left| X \right| \left| Y \right|}.

This notion was originally introduced by Thomason. Jumbled graphs are quite ubiquitous. For example, the Erdös-Rényi random graph {G_{n,p}}, formed by taking an empty graph on {n} vertices and adding each edge independently with probability {p}, is, with high probability, {(p, \beta)}-jumbled with {\beta = O(\sqrt{pn})}. We remark that many extremal and Ramsey problems on sparse random graphs have been resolved by recent breakthroughs of Conlon and Gowers, and independently Schacht, and they also follow more generally from the KŁR conjecture, which has also been resolved very recently. However, the techniques used for random graphs do not immediately transfer over to pseudorandom graphs.

One particularly well-known class of {(p, \beta)}-jumbled graphs is the collection of {(n, d, \lambda)}-graphs. These are graphs on {n} vertices which are {d}-regular and such that all eigenvalues of the adjacency matrix, except for the largest, are at most {\lambda} in absolute value. The famous expander mixing lemma tells us that these graphs are {(p, \beta)}-jumbled with {p = d/n} and {\beta = \lambda}. An explicit example of such a graph is the Paley graph with vertex set {{\mathbb Z}_p}, where {p \equiv 1 (\mbox{mod } 4)} is prime, and edge set given by connecting {x} and {y} if their difference is a quadratic residue is such a graph with {p = \frac{1}{2}} and {\beta = O(\sqrt{n})}. Pseudorandom graphs have many surprising properties and applications and have recently attracted a lot of attention both in combinatorics and theoretical computer science. For more, see the wonderful survey by Krivelevich and Sudakov.

Now let us discuss some of our extremal results for sparse pseudorandom graphs.

Mantel’s theorem tells us that every triangle-free graph {G} on {n} vertices has at most {\frac{n^2}{4}} edges. More generally, Turán’s theorem tells us that every {K_{r+1}}-free graph {G} on {n} vertices has at most {\frac{r-1}{r}\frac{n^2}{2}} edges. And even more generally, the Erdös-Stone-Simonovitstheorem tells us that for any fixed graph {H}, any {H}-free graph {G} on {n} vertices has at most

\displaystyle \left( 1 - \frac{1}{\chi(H) - 1} + o(1) \right) \binom{n}{2}

edges, where {\chi(H)} is the chromatic number of {H}. We extend this result to sparse pseudorandom graphs. In the following statement, {d(H)} is the degeneracy of {H}, and {e(\Gamma)} is the number of edges in {\Gamma}. For specific {H} we often have better bounds on {\beta}, and the same is true for our other results.

Theorem 1 (Sparse Erdös-Stone-Simonovits) For every graph {H} and every {\epsilon > 0}, there exists {c > 0} such that if {\beta \leq cp^{d(H) + \frac{5}{2}} n} then any {(p,\beta)}-jumbled graph {\Gamma} on {n} vertices has the property that any {H}-free subgraph of {\Gamma} has at most

\displaystyle \left( 1 - \frac{1}{\chi(H) - 1} + o(1) \right) e(\Gamma).

edges.

A basic example in Ramsey theory is that for any coloring of the edges of a {K_6} with two colors, there is always a monochromatic triangle. More generally, Ramsey’s theorem tells us that for any graph {H} and positive integer {r}, if {n} is sufficiently large, then any {r}-coloring of the edges of {K_n} contains a monochromatic copy of {H}. We extend Ramsey’s theorem to the sparse pseudorandom graphs.

Theorem 2 (Sparse Ramsey) For every graph {H} and every positive integer {r \geq 2}, there exists {c > 0} such that if {\beta \leq cp^{d(H) + \frac{5}{2}}} then any {(p, \beta)}-jumbled graph {\Gamma} on {n} vertices has the property that any {r}-coloring of the edges of {\Gamma} contains a monochromatic copy of {H}.

One of the simplest proofs of Roth’s theorem (Szemerédi’s theorem for 3-term arithmetic progressions) is via the triangle removal lemma, which says that every graph on {n} vertices with at most {o(n^3)} triangles can be made triangle-free by deleting at most {o(n^2)} edges. More generally, the graph removal lemma states that for every fixed graph {H} and every {\epsilon > 0}, there exists {\delta > 0} such that if {G} contains at most {\delta n^{v(H)}} copies of {H} then {G} may be made {H}-free by removing at most {\epsilon n^2} edges. We extend this result to the sparse setting.

Theorem 3 (Sparse graph removal) For every graph {H} and every {\epsilon > 0}, there exist {\delta > 0} and {c > 0} such that if {\beta \leq cp^{d(H) + \frac{5}{2}}} then any {(p, \beta)}-jumbled graph {\Gamma} on {n} vertices has the following property: any subgraph of {\Gamma} containing at most {\delta p^{e(H)}n^{v(H)}} copies of {H} may be made {H}-free by removing at most {\epsilon pn^2} edges.

In our paper, we use the sparse graph removal result to give a sparse extension of a removal lemma for groups, which implies an extension of Roth’s theorem.

The key technical result in our paper is the counting lemma for sparse pseudorandom graphs. It is the tool that allows us to transfer these classical results to the sparse setting. For a precise statement of the counting lemma, as well as discussions of further applications, we invite you to read our paper.

Advertisements