These are lecture notes for a class on Extremal Graph Theory by Asaf Shapira.
The notes are available from here.
Change Log
28/12/2013: Typos in several equations.
13/03/2015: Fixed a typo.
Table of contents
1 First Lecture
1.1 Mantel’s Theorem
1.2 Turán’s Theorem
1.3 Ramsey’s Theorem
2 Second Lecture
2.1 The Erdős-Stone-Simonovits Theorem
2.2 The Zarankiewicz Problem for K2,2
2.3 The Zarankiewicz Problem for General Ks,t
3 Third Lecture
3.1 Applications of the Zarankiewicz Problem
3.2 The Turán Problem for Trees
3.3 The Girth Problem and Moore’s Bound
3.4 Application of Moore’s Bound to Graph Spanners
4 Fourth Lecture
4.1 The Turán Problem for Long Cycles
4.2 Pancyclic Graphs and Bondy’s Theorem
4.3 The Moon-Moser Inequalities
5 Fifth Lecture
5.1 The Hypergraph Turán Problem
5.2 Extremal Problems Related to Graph Minors
5.3 Application of Topological Kt -Minors to Graph Linkage
6 Sixth Lecture
6.1 Introduction to Szemerédi’s Regularity Lemma
6.2 The Triangle-Removal Lemma and Roth’s Theorem
6.3 Proof of the Regularity Lemma
7 Seventh Lecture
7.1 The Counting Lemma
7.2 Another Proof of the Erdős-Stone-Simonovits Theorem
7.3 Ramsey Numbers of Bounded Degree Graphs
8 Eighth Lecture
8.1 The Induced Ramsey Theorem
8.2 The (6, 3)-Problem and the Induced Matchings Problem
9 Ninth Lecture
9.1 Behrend’s Construction
9.2 Lower Bound for the Triangle Removal Lemma
9.3 Deducing Szemerédi’s Theorem from the Hypergraph Removal Lemma
10 Tenth Lecture
10.1 The Ramsey-Turán Problem
10.2 Quasi-Random Graphs
11 Eleventh Lecture
11.1 The Chung-Graham-Wilson Theorem
11.2 An Algorithmic Version of the Regularity Lemma
11.3 Approximating MAX-CUT using the Regularity Lemma
12 Twelfth lecture
12.1 Hypergraph Ramsey Numbers