**Extremal Combinatorics**

- 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

Final Exam information

*If you wish to take the final, please register.**How to register: send an email with title “ECOPRO-Spring2024-Name+University” to Zhuo.Wu@warwick.ac.uk.**Deadline: 5/21 mid-night everywhere in the world.*

*Final exam will be on Saturday 5/25 8:30-11:30am (Beijing),*.*9:30am-12:30pm (Seoul)**It is an online exam, hosted on the same zoom:***346 934 4087, PW: 202402***When entering the zoom, please change id to: “Name + University”**The zoom room will be open 20 minutes before the exam. Please make sure to enter before 8:30am (Beijing)=9:30am (Seoul). No late admission is allowed.**The final exam problem sheet will be posted 10 minutes before the exam via a link in the zoom chat.**Please take the exam using our designated answer sheet. You can download and print out the answer sheet beforehand. Download Answer Sheet*

*Examinable material: Lecture 1 — Lecture 21.**Exam rules. During the online exam, please adhere to the following rules, otherwise it will be considered cheating.**This is a closed book exam. Do not place textbooks, exercise books, or any irrelevant materials on the desk.**Prepare two devices to log in zoom (laptop+phone) both with the same id “Name+Uni”.**Turn on the cameras on your phone and computer at the same time. While the computer’s camera is facing the test taker, place the phone camera on the side, about 50-100cm away, so that the test taker’s face, hands, and desk surface are clearly visible. Keep the Zoom video on your phone active during the exam.**Keep your computer from going to sleep or activating screen savers. During the exam, you are not allowed to operate the computer or phone.**At the end of the exam, take photos of the answer sheets with your phone, then merge them into a PDF file (you can use scanning apps like “Scanner Pro”). Please make sure to send the PDF file to*within 10 minutes after the exam. No late submission will be allowed. If it’s not convenient to merge the sheets into a PDF, you can directly send the numbered images to the invigilator.*Zhuo.Wu@warwick.ac.uk**Zoom and device testing. We will open the same zoom on 5/24 Friday 7:30-7:50pm Beijing = 8:30-8:50pm Seoul evening if you wish to check your cameras and other devices.*

#### 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**