Extremal Graph Theory  (Fall 2023)
Grading: I will hand out several sets of exercises which
will be graded.
Lecture Notes
Home Assignments
Tentative list of Topics (to be updated during the semester)

Lecture 1:
Four proofs of Mantel's Theorem, three proofs of Turan's Theorem, two
upper bounds for Ramsey numbers, and one lower bound.

Lecture 2:
The ErdosStoneSimonovits Theorem. The Zarankiewicz Problem
(upper/lower bounds for general K_st, and tight ones for K_22).

Lecture 3:
Applications of the Zarankiewicz Problem: the Unit Distance Problem, and
Small Additive Basis for Squares. Turan Problem for Trees. Dirac's Theorem
and the Turan Problem for Paths (ErdosGallai Theorem). Upper/Lower
bounds for the Girth Problem (Moore Bound) and its application to Graph
Spanners. Large bipartite subgraphs.

Lecture 4:
Turan Problem for Long Cycles (ErdosGallai Theorem). Bondy's
Theorem on Pancyclic Graphs. The MoonMoser Inequality and it's
application to Supersaturated graphs.

Lecture 5:
Lower/Upper bounds for Hypergraph Turan Problem. Extremal Problem
for K_tMinor and Topological K_tMinor. High Connectivity implies High
Linkage.

Lecture 6:
Szemeredi's Regularity Lemma, The Removal Lemma and Roth's Theorem.

Lecture 7:
Embedding small subgraphs into regular graphs (aka Counting Lemma).
Applications of the Regularity
Lemma: ErdosStone Theorem, and Ramsey numbers of
bounded degree graphs (BurrErdos Conjecture).

Lecture 8:
More applications of the Regularity Lemma: Induced Ramsey Theorem, the
(6,3)Problem and the Induced Matching Problem.

Lecture 9:
Behrend's construction and a lower bound for the Triangle Removal Lemma.
Deriving Szemeredi's Theorem from the Hypergraph Removal Lemma.

Lecture 10:
The RamseyTuran Problem for K_3, K_4 and K_5. Properties of QuasiRandom
Graphs and some simple equivalences between them.

Lecture 11:
The ChungGrahamWilson Theorem (C_4density forces QuasiRandomness).
Algorithmic version of the Regularity Lemma
(AlonDukeLefmanRodlYuster). Approximating MaxCut using the Regularity
Lemma.

Lecture 12:
Hypergraph Ramsey Numbers; the ErdosRado upper bound and the ErdosHajnal
lower bound (aka SteppingUp Lemmas).