## Topics in Extremal Combinatorics

- Time: every Monday and Wednesday 10:00-11:30am (KST), September 26 – January 11, 2023.
- Zoom: 346 934 4087, PW: 202209

#### Announcement

- We will have the class at 12pm-1pm (KST) on Monday October 31.
**The classes on December 21, 26, 28 and January 2, 4 will be at 5pm-6:30pm (KST).**

**Part 1. Turán type problem**

- 9/26 Lecture 1: extremal number, Mantel’s thm, Turán’s thm, Caro-Wei.
**Tablet note** - 9/28 Lecture 2: applications of Turán’s thm, symmetrization method: Zykov, Motzkin-Straus.
**Tablet note** - 10/3 Lecture 3: applications of symmetrization: Erdős-Rothschild problem, weighted Turán, bounding largest eigenvalue via Frobenius norm.
**Tablet note** - 10/5 Lecture 4: multicolor symmetrization of Füredi-Maleki, minimize triangular edges, Erdős-Simonovits-Stone.
**Tablet note** - 10/10 Lecture 5: supersaturation, $r$-uniform $r$-partite hypergraph has Turán density 0, blowups of a graph have the same Turán density, supersaturation ⇒ Erdős-Simonovits-Stone.
**Tablet note** - 10/12 Lecture 6: Moon-Moser ⇒ supersaturation, Nikiforov: positive $K_r$-density ⇒ $\log n$-blowup of $K_r$.
**Tablet note** - 10/17 Lecture 7: Füredi’s perfect stability for cliques + Removal lemma ⇒ Erdős-Simonovits stability.
**Tablet note** - 10/19 Lecture 8: Extremal number of odd cycle via stability method, triangle case of Andrasfai-Erdős-Sós.
**Tablet note** - 10/24 Lecture 9: Brandt’s pf of Andrasfai-Erdős-Sós, chromatic threshold, Hajnal’s contruction of dense triangle-free graphs with large chromatic number via Kneser graphs.
**Tablet note** - 10/26 Lecture 10: Chromatic threshold of odd cycles are 0, homomorphism threshold.
**Tablet note** - 10/31 Lecture 11: No induced cube in dense maximal triangle-free graphs, chromatic threshold of triangle via VC dimension.
**Tablet note** - 11/2 Lecture 12: Homomorphism threshold of triangle.
**Tablet note**

**Part 2. Bipartite Turán**

- 11/7 Lecture 13: $C_4$-free graphs and Sidon sets, Kővári-Sós-Turán, application to unit distance problem, dense $K_{2,2}$-, $K_{3,3}$-free construction.
**Tablet note** - 11/9 Lecture 14: Bondy-Simonovits, even cycle via BFS.
**Tablet note** - 11/14 Lecture 15: Regularisation for bipartite Turán, Füredi-Alon-Krivelevich-Sudakov: bipartite graphs with bounded degree, dependent random choice.
**Tablet note** - 11/16 Lecture 16: Random zooming method, applications: Füredi-Alon-Krivelevich-Sudakov, 1-subdivision of $\sqrt{n}$-clique in dense graphs, Conlon-Lee conjecture on $K_{r,r}$-free $r$-bounded bipartite $H$.
**Tablet note** - 11/21 Lecture 17: Upper bound on extremal number of 1-subdivision of $K_t$.
**Tablet note** - 11/23 Lecture 18: Sidorenko’s conjecture for $P_3$ and even cycles.
**Tablet note** - 11/28 Lecture 19: Equivalence of Erdős-Simonovits conjecture and Sidorenko’s conjecture via tensor power trick, 2nd pf even cycle via Sidorenko’s conjecture.
**Tablet note** - 11/30 Lecture 20: Cube with a diagonal, Erdős-Simonovits reduction trick, 3rd pf even cycle via iterative Cauchy-Schwarz and Sidorenko.
**Tablet note** - 12/5 Lecture 21: Other applications of iterative Cauchy-Schwarz and Sidorenko: hypercube, rainbow cycles.
**Tablet note** - 12/7 Lecture 22: Cylindrical grid via supersaturation, even cycle embedding without conflict via dyatic partition.
**Tablet note** - 12/12 Lecture 23: Cylinder $C_{2k}\square K_2$.
**Tablet note** - 12/14 Lecture 24: Bukh’s dense $K_{s,t}$-free graphs via random algebraic construction, rational Turán exponent conjecture, powers of rooted trees.
**Tablet note** - 12/19 Lecture 25: Bukh-Conlon rational exponent for powers of balanced rooted trees, subdivision conjecture.
**Tablet note** - 12/21 Lecture 26: Subdivision conjecture implies rational Turán exponent conjecture, constructing multiplicative Sidon sets using $C_4$-free graphs.
**Tablet note** - 12/26 Lecture 27: Counting multiplicative Sidon sets via asymmetric $C_4$-free graphs.
**Tablet note**

**Part 3. Szemerédi Regularity Lemma**

- 12/28 Lecture 28: Regular pair, regular parititon, most vertices are typical in a regular pair, slicing lemma.
**Tablet note** - 1/2 Lecture 29: Reduced graph, embedding/counting/removal lemmas.
**Tablet note** - 1/4 Lecture 30: Removal lem ⇒ (6,3)-thm ⇒ Roth’s thm, Brown-Erdős-Sós (e+3, e)-conjecture.
**Tablet note** - 1/9 Lecture 31: Induced matching thm ⇒ (6,3)-thm, Ramsey-Turán for $K_4$.
**Tablet note** - 1/11 Lecture 32: $C_6$-free point/line incidence graphs, linear ramsey number for bounded degree graphs.
**Tablet note**