Extremal Graph Theory

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

Leave a Reply

Your email address will not be published. Required fields are marked *