Extremal Combinatorics I

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

Final exam

Announcement

• The last two classes on 6/11 & 6/13 will be at 13:30-15:00 (Beijing), 14:30-16:00pm (Seoul).
• There will be a summer research program at ECOPRO in July and August of this year.
• The Thursday class on June 6 will be switched to the same time on Friday June 7.
• The Tuesday class on June 4 will be switched to the same time on Monday June 3.
• There is no class on Thursday 5/23.
• There is no class on Thursday 5/2.
• 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).

---

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

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
• 4/30 Lecture 17: Erdős-Ko-Rado, Katona’s pf, counting intersecting uniform families. Tablet note
• 5/7 Lecture 18: Counting maximal intersecting uniform families via Bollobás set-pairs ineq, colexicographic order, shadow, Kruskal-Katona. Tablet note
• 5/9 Lecture 19: Pf Kruskal-Katona via shifting, VC dimension. Tablet note
• 5/14 Lecture 20: 3 pfs of Sauer-Shelah, Dimension argument. Tablet note
• 5/16 Lecture 21: De Bruijn-Erdős, sets with at most two distinct distances, Frankl-Wilson forbidding a single intersection size. Tablet note
• 5/21 Lecture 22: Application of Frankl-Wilson: sets with no orthogonal pairs, Kahn-Kalai on Borsuk’s conjecture, Katona’s intersection thm. Tablet note

---

3. Szemerédi’s Regularity Lemma

• 5/28 Lecture 23: Regular pair, regular partition, Szemerédi’s regularity lemma, slicing lemma, reduced graph. Tablet note
• 5/30 Lecture 24: Embedding lemma, counting lemma, Ramsey-Turán for $K_4$. Tablet note
• 6/3 Lecture 25: Multicolor regularity lemma, Chvátal-Rödl-Szemerédi-Trotter bdd deg graph Ramsey number linear, Ruzsa-Szemerédi triangle removal lemma. Tablet note
• 6/7 Lecture 26: Triangle removal lemma ⇒ (6,3)-thm ⇒ Roth’s thm, Induced matching thm ⇒ (6,3)-thm. Tablet note
• 6/11 Lecture 27: Pf induced matching thm, pts/lines incidence graphs, Matoušek’s cutting lemma. Tablet note
• 6/13 Lecture 28: Application of removal lemma on $C_6$-free pts/lines incidence graph, Regularity lemma as containers, counting $K_{r+1}$-free graphs on $[n]$, linear-size clique in dense graphs with no induced $C_4$. Tablet note

---