**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).

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**: Application of Dilworth: better Ramsey for intersection graph of planar convex sets.**Tablet note**