Autumn 2022

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

---