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:
- Starting with any graph , apply Szemerédi’s regularity lemma to obtain a regular partition;
- Clean up the graph and create an associated reduced graph. Solve an easier problem in the reduced graph;
- 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 is –jumbled if for all vertex subsets and of , we have
This notion was originally introduced by Thomason. Jumbled graphs are quite ubiquitous. For example, the Erdös-Rényi random graph , formed by taking an empty graph on vertices and adding each edge independently with probability , is, with high probability, -jumbled with . 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 -jumbled graphs is the collection of -graphs. These are graphs on vertices which are -regular and such that all eigenvalues of the adjacency matrix, except for the largest, are at most in absolute value. The famous expander mixing lemma tells us that these graphs are -jumbled with and . An explicit example of such a graph is the Paley graph with vertex set , where is prime, and edge set given by connecting and if their difference is a quadratic residue is such a graph with and . 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 on vertices has at most edges. More generally, Turán’s theorem tells us that every -free graph on vertices has at most edges. And even more generally, the Erdös-Stone-Simonovitstheorem tells us that for any fixed graph , any -free graph on vertices has at most
edges, where is the chromatic number of . We extend this result to sparse pseudorandom graphs. In the following statement, is the degeneracy of , and is the number of edges in . For specific we often have better bounds on , and the same is true for our other results.
Theorem 1 (Sparse Erdös-Stone-Simonovits) For every graph and every , there exists such that if then any -jumbled graph on vertices has the property that any -free subgraph of has at most
A basic example in Ramsey theory is that for any coloring of the edges of a with two colors, there is always a monochromatic triangle. More generally, Ramsey’s theorem tells us that for any graph and positive integer , if is sufficiently large, then any -coloring of the edges of contains a monochromatic copy of . We extend Ramsey’s theorem to the sparse pseudorandom graphs.
Theorem 2 (Sparse Ramsey) For every graph and every positive integer , there exists such that if then any -jumbled graph on vertices has the property that any -coloring of the edges of contains a monochromatic copy of .
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 vertices with at most triangles can be made triangle-free by deleting at most edges. More generally, the graph removal lemma states that for every fixed graph and every , there exists such that if contains at most copies of then may be made -free by removing at most edges. We extend this result to the sparse setting.
Theorem 3 (Sparse graph removal) For every graph and every , there exist and such that if then any -jumbled graph on vertices has the following property: any subgraph of containing at most copies of may be made -free by removing at most 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.