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 Erdos-Stone-Simonovits 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 (Erdos-Gallai 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 (Erdos-Gallai Theorem). Bondy's
Theorem on Pancyclic Graphs. The Moon-Moser Inequality and it's
application to Supersaturated graphs.
-
Lecture 5:
Lower/Upper bounds for Hypergraph Turan Problem. Extremal Problem
for K_t-Minor and Topological K_t-Minor. 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: Erdos-Stone Theorem, and Ramsey numbers of
bounded degree graphs (Burr-Erdos 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 Ramsey-Turan Problem for K_3, K_4 and K_5. Properties of Quasi-Random
Graphs and some simple equivalences between them.
-
Lecture 11:
The Chung-Graham-Wilson Theorem (C_4-density forces Quasi-Randomness).
Algorithmic version of the Regularity Lemma
(Alon-Duke-Lefman-Rodl-Yuster). Approximating Max-Cut using the Regularity
Lemma.
-
Lecture 12:
Hypergraph Ramsey Numbers; the Erdos-Rado upper bound and the Erdos-Hajnal
lower bound (aka Stepping-Up Lemmas).