Extremal Combinatorics

Time: From March 5th, 2024, every Tuesday and Thursday
8:30-10:00am (Beijing), 9:30-11:00am(Seoul).
Zoom: 346 934 4087, PW: 202402

Announcement

There will be a summer research program at ECOPRO in July and August of this year.
The Tuesday class on 4/16 will be switched to the same time on Monday April 15.
The class on 3/12 will be at 10am-11:30am (Beijing), 11am-12:30pm (Seoul).

Note

Videos

YouTube

Final grade: Homeworks 50%, exam 50%. Please send homework to Zhuo.Wu@warwick.ac.uk

HW 1

HW 2

HW 3

Part 1. Topics

1. Turán problem

3/5 Lecture 1: graph, handshaking lemma, common graph families, subgraph, large degree ⇒ long cycle & large trees, Mantel’s thm, pf1 induction, pf2 max-deg vertex, odd/even town via linear algebra, lower bd construction for Ramsey via probabilistic method. Tablet note
3/7 Lecture 2: Erdős-Szekeres monotone seq via pigeonhole, Sperner’s thm via LYM ineq, pf1 double counting, pf2 probabilistic counting, extremal number, Turán graph, Turán’s thm, pf1 induction, pf2 max-deg vertex, pf3 Zykov’s symmetrization. Tablet note
3/12 Lecture 3: Turán’s thm, pf4 Motzkin-Straus Symmetrization, pf5 probabilistic pf Caro-Wei, first moment method, Erdős-Stone-Simonovits thm pf1. Tablet note
3/14 Lecture 4: a geometric application of Turán’s thm, homomorphism, an embedding lemma bootstrapping $H$-freeness to $H$-hom-freeness, a modern pf2 of Erdős-Stone-Simonovits thm, supersaturation phenomenon, Turán density exists for every graph. Tablet note
3/19 Lecture 5: $r$-uniform $r$-partite hypergraph has Turán density 0, supersaturation pf1 local averaging, supersaturation ⇒ blowups of a graph has the same Turán density ⇒ pf3 Erdős-Simonovits-Stone, Moon-Moser ⇒ supersaturation pf2. Tablet note
3/21 Lecture 6: Füredi perfect stability via degree majorization, Erdős-Simonovits stability from perfect stability and Ruzsa-Szemerédi removal lemma, stability method. Tablet note
3/26 Lecture 7: extremal number of $C_5$ via stability, every maximal $K_r$-free graph contains a wheel-like graph, Brandt’s pf of Andrasfai-Erdős-Sós. Tablet note
3/28 Lecture 8: Bipartite Turán problem, $C_4$ and Sidon-set, Kővári-Sós-Turán, dense constructions of $C_4$-free and $K_{3,3}$-free graphs, Bondy-Simonovits on extremal number of even cycles, pf1 using BFS. Tablet note
4/2 Lecture 9: Regularization, bipartite graph with bounded degree, random zooming. Tablet note
4/4 Lecture 10: Sidorenko’s conjecture, $P_3, C_4$, even cycles, pf2 of even cycle extremal number upper bound using Sidorenko. Tablet note
4/9 Lecture 11: 3-dim cube via supersaturation, grid via rich collection of paths, pf3 of even cycle via Sidorenko and iterative Cauchy-Schwarz. Tablet note

2. Extremal Set Theory

4/11 Lecture 12: Bollobás set-pairs ineq, pf via random permutation, skewed version via exterior algebra, applications: 1. LYM ineq, 2. saturation number. Tablet note
4/15 Lecture 13: Application of Sperner: Littlewood-Offord, Poset, height, width, Dilworth’s thm, pf1 induction, Mirsky’s thm. Tablet note
4/18 Lecture 14: Dilworth pf2 symm chain decomposition, pf3 Kőnig’s thm, Application of Dilworth: better Ramsey for interval graphs and intersection graphs of planar convex sets. Tablet note
4/23 Lecture 15: Ramsey for intersection graph of rectangles in the plane via Dilworth, Erdős-Rado’s sunflower lemma. Tablet note
4/25 Lecture 16: Harris-Kleitman correlation inequality and applications on intersecting families. Tablet note