Graph theory and additive combinatorics: exploring structure and randomness

Contents
Preface
Notation and Conventions
0 Appetizer: Triangles and Equations
	0.1 Schur’s Theorem
	0.2 Progressions
	0.3 What’s Next in the Book?
1 Forbidding a Subgraph
	1.1 Forbidding a Triangle: Mantel’s Theorem
	1.2 Forbidding a Clique: Turán’s Theorem
	1.3 Turán Density and Supersaturation
	1.4 Forbidding a Complete Bipartite Graph: Kovári–Sós–Turán Theorem
	1.5 Forbidding a General Subgraph: Erdos–Stone–Simonovits Theorem
	1.6 Forbidding a Cycle
	1.7 Forbidding a Sparse Bipartite Graph: Dependent Random Choice
	1.8 Lower Bound Constructions: Overview
	1.9 Randomized Constructions
	1.10 Algebraic Constructions
	1.11 Randomized Algebraic Constructions
2 Graph Regularity Method
	2.1 Szemerédi’s Graph Regularity Lemma
	2.2 Triangle Counting Lemma
	2.3 Triangle Removal Lemma
	2.4 Graph Theoretic Proof of Roth’s Theorem
	2.5 Large 3-AP-Free Sets: Behrend’s Construction
	2.6 Graph Counting and Removal Lemmas
	2.7 Exercises on Applying Graph Regularity
	2.8 Induced Graph Removal and Strong Regularity
	2.9 Graph Property Testing
	2.10 Hypergraph Removal and Szemerédi’s Theorem
	2.11 Hypergraph Regularity
3 Pseudorandom Graphs
	3.1 Quasirandom Graphs
	3.2 Expander Mixing Lemma
	3.3 Abelian Cayley Graphs and Eigenvalues
	3.4 Quasirandom Groups
	3.5 Quasirandom Cayley Graphs and Grothendieck’s Inequality
	3.6 Second Eigenvalue: Alon–Boppana Bound
4 Graph Limits
	4.1 Graphons
	4.2 Cut Distance
	4.3 Homomorphism Density
	4.4 W-Random Graphs
	4.5 Counting Lemma
	4.6 Weak Regularity Lemma
	4.7 Martingale Convergence Theorem
	4.8 Compactness of the Graphon Space
	4.9 Equivalence of Convergence
5 Graph Homomorphism Inequalities
	5.1 Edge versus Triangle Densities
	5.2 Cauchy–Schwarz
	5.3 Hölder
	5.4 Lagrangian
	5.5 Entropy
6 Forbidding 3-Term Arithmetic Progressions
	6.1 Fourier Analysis in Finite Field Vector Spaces
	6.2 Roth’s Theorem in the Finite Field Model
	6.3 Fourier Analysis in the Integers
	6.4 Roth’s Theorem in the Integers
	6.5 Polynomial Method
	6.6 Arithmetic Regularity
	6.7 Popular Common Difference
7 Structure of Set Addition
	7.1 Sets of Small Doubling: Freiman’s Theorem
	7.2 Sumset Calculus I: Ruzsa Triangle Inequality
	7.3 Sumset Calculus II: Plünnecke’s Inequality
	7.4 Covering Lemma
	7.5 Freiman’s Theorem in Groups with Bounded Exponent
	7.6 Freiman Homomorphisms
	7.7 Modeling Lemma
	7.8 Iterated Sumsets: Bogolyubov’s Lemma
	7.9 Geometry of Numbers
	7.10 Finding a GAP in a Bohr Set
	7.11 Proof of Freiman’s Theorem
	7.12 Polynomial Freiman–Ruzsa Conjecture
	7.13 Additive Energy and the Balog–Szemerédi–Gowers Theorem
8 Sum-Product Problem
	8.1 Multiplication Table Problem
	8.2 Crossing Number Inequality and Point-Line Incidences
	8.3 Sum-Product via Multiplicative Energy
9 Progressions in Sparse Pseudorandom Sets
	9.1 Green–Tao Theorem
	9.2 Relative Szemerédi Theorem
	9.3 Transference Principle
	9.4 Dense Model Theorem
	9.5 Sparse Counting Lemma
	9.6 Proof of the Relative Roth Theorem
References
Index