Extremal results in sparse pseudorandom graphs

Abstract

Szemerédi's regularity lemma is a fundamental tool in extremal combinatorics. However, the original version is only helpful in studying dense graphs. In the 1990s, Kohayakawa and Rödl proved an analogue of Szemerédi's regularity lemma for sparse graphs as part of a general program toward extending extremal results to sparse graphs. Many of the key applications of Szemerédi's regularity lemma use an associated counting lemma. In order to prove extensions of these results which also apply to sparse graphs, it remained a well-known open problem to prove a counting lemma in sparse graphs. The main advance of this paper lies in a new counting lemma, proved following the functional approach of Gowers, which complements the sparse regularity lemma of Kohayakawa and Rödl, allowing us to count small graphs in regular subgraphs of a sufficiently pseudorandom graph. We use this to prove sparse extensions of several well-known combinatorial theorems, including the removal lemmas for graphs and groups, the Erdős-Stone-Simonovits theorem and Ramsey's theorem. These results extend and improve upon a substantial body of previous work.

70 pages, accepted for publication in Adv. Math

References in corpus (7)

• A Szemeredi-type regularity lemma in abelian groups, with applications
• The Clique Density Theorem
• Hypergraph regularity and the multidimensional Szemerédi theorem
• On the KŁR conjecture in random graphs
• On the logarithimic calculus and Sidorenko's conjecture
• Extremal results for odd cycles in sparse pseudorandom graphs
• Szemerédi's Regularity Lemma for matrices and sparse graphs

Cited by in corpus (27)

• An $L^p$ theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions
• On replica symmetry of large deviations in random graphs
• On the KŁR conjecture in random graphs
• A relative Szemerédi theorem
• Combinatorial theorems relative to a random set
• The Green-Tao theorem: an exposition
• The regularity method for graphs with few 4-cycles
• A sequence of triangle-free pseudorandom graphs
• Near-perfect clique-factors in sparse pseudorandom graphs
• Counting results for sparse pseudorandom hypergraphs II
• Forcing quasirandomness with triangles
• Finding any given 2-factor in sparse pseudorandom graphs efficiently
• Counting results for sparse pseudorandom hypergraphs I
• Regularity inheritance in hypergraphs
• Exploring Projective Norm Graphs
• Discrepancy and Eigenvalues of Cayley Graphs
• Sparse graph counting and Kelley-Meka bounds for binary systems
• Regularity inheritance in pseudorandom graphs
• Additive combinatorics with a view towards computer science and cryptography: An exposition
• An extension of Mantel's theorem to random 4-uniform hypergraphs
• Turán problems in pseudorandom graphs
• Powers of Hamilton cycles in pseudorandom graphs
• A counterexample to the Bollobás-Riordan conjectures on sparse graph limits
• Hamiltonicity of Sparse Pseudorandom Graphs
• Which graphs can be counted in $C_4$-free graphs?
• Odd cycles in subgraphs of sparse pseudorandom graphs
• Turan numbers for bipartite graphs plus an odd cycle