Extremal Graph Theory - (Fall 2016)
Grading: I will hand out several sets of exercises which
will be graded.
Tentative list of Topics (to be updated during the semester)
Four proofs of Mantel's Theorem, three proofs of Turan's Theorem, two
upper bounds for Ramsey numbers, and one lower bound.
The Erdos-Stone-Simonovits Theorem. The Zarankiewicz Problem
(upper/lower bounds for general K_st, and tight ones for K_22).
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.
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.
Lower/Upper bounds for Hypergraph Turan Problem. Extremal Problem
for K_t-Minor and Topological K_t-Minor. High Connectivity implies High
Szemeredi's Regularity Lemma, The Removal Lemma and Roth's Theorem.
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).
More applications of the Regularity Lemma: Induced Ramsey Theorem, the
(6,3)-Problem and the Induced Matching Problem.
Behrend's construction and a lower bound for the Triangle Removal Lemma.
Deriving Szemeredi's Theorem from the Hypergraph Removal Lemma.
The Ramsey-Turan Problem for K_3, K_4 and K_5. Properties of Quasi-Random
Graphs and some simple equivalences between them.
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
Hypergraph Ramsey Numbers; the Erdos-Rado upper bound and the Erdos-Hajnal
lower bound (aka Stepping-Up Lemmas).