Extremal Combinatorics II

Time: From September 24, 2024 — January 6, 2025, every Tuesday and Thursday
8:30-10:00 (Beijing), 9:30-11:00 (Seoul).
Zoom: 346 934 4087, PW: 202409

The class on January 7, 2025, is moved to January 6, 2025, in the afternoon 15:30-17:00 (Beijing), 16:30-18:00 (Seoul).
No class on December 12. Classes resume on December 17.
The class on December 10 is moved to the afternoon 15:30-17:00 (Beijing), 16:30-18:00 (Seoul).
The class on November 5 is moved to November 4.
No class on October 1 & 3. Classes resume on October 8.

Part 2. Methods

9/24 Lecture 1: Entropy, joint/conditional entropy, quick application: volume of Hamming ball, Shannon-Khinchin axioms, independence, monotonicity, non-negativity. Tablet note
9/26 Lecture 2: Dependence, chain rule, dropping conditioning, subadditivity, Shearer’s lem, application: Loomis-Whitney ineq. Tablet note
10/8 Lecture 3: Equivalence of funct defn and axiom defn of entropy, application: triangle maximization, triangle intersecting family. Tablet note
10/10 Lecture 4: Brégman’s thm, Sidorenko’s conj for star of size 2. Tablet note
10/15 Lecture 5: $H$-colorings, counting independent sets, counting matroids. Tablet note
10/17 Lecture 6: Mantel’s thm, Goodman’s bound, Moon-Moser, Han’s ineq, Harper’s edge-isoperimetric ineq for hypercube. Tablet note
10/22 Lecture 7: Kruskal-Katona thm, union-closed conj. Tablet note

10/24 Lecture 8: Counting problems, Kleitman-Winston graph container thm. Tablet note
10/29 Lecture 9: Counting intersecting families, hypergraph container for triangle-free graphs, counting triangle-free graphs. Tablet note
10/31 Lecture 10: Counting maximal triangle-free graphs, maximal independent sets, maximal sum-free sets. Tablet note
11/4 Lecture 11: Counting the number of maximal sum-free sets. Tablet note
11/7 Lecture 12: Number of independent sets in regular graphs that are far from bipartite, counting $C_4$-free graphs. Tablet note
11/12 Lecture 13: Random analogue of Mantel & Schur’s thm. Tablet note
11/14 Lecture 14: Balogh-Solymosi points in general position in the plane. Tablet note

11/19 Lecture 15: Supersaturation for colinear triples in $[m]^3$, random block construction, Ramsey $K_4$ vs clique. Tablet note
11/21 Lecture 16: $r(4,t)\ge ct^3/\log^4t$, unital in projective plane, multicolor Ramsey $r_k(4;t)$. Tablet note
11/26 Lecture 17: Erdős-Roger function, $f_{3,4}(n)\le \sqrt{n}(\log n)^{120}$. Tablet note
11/28 Lecture 18: Behrend’s 3-AP-free construction, Green’s corner-free set, Erdős-Rothschild problem on book. Tablet note
12/3 Lecture 19: Using high dim grid: 1)Erdős-Rothschild book problem; 2) almost complete graph covered by almost linear-size induced matchings. Tablet note
12/5 Lecture 20: Bollobás-Erdős graphs, complex spheres. Tablet note
12/10 Lecture 21: Complex Bollobás-Erdős graphs, lower bound on multicolor Ramsey. Tablet note

12/17 Lecture 22: First moment, exponentially many well-separated sets, large sum-free subset, Markov’s inequality, graphs with large girth and chromatic number. Tablet note
12/19 Lecture 23: Concentration of measure, crossing lem via sampling, Szemerédi-Trotter pts/lines incidences, unit distance problem. Tablet note
12/24 Lecture 24: Alteration, threshold function for $G(n,p)$ containing a triangle, 2nd moment, Chebyshev’s inequality, Rödl Nibble, Pippenger-Spencer, independent sets in triangle-free graphs. Tablet note
12/26 Lecture 25: Nibble step in Ajtai-Komlós-Szemerédi, dependent random choice, phase transition of Ramsey-Turán number of $K_5$ at $\sqrt{n\log n}$: $\mathrm{RT}(n,K_5,o(\sqrt{n\log n}))=o(n^2)$. Tablet note
12/31 Lecture 26: $\mathrm{RT}(n,K_8,o(\sqrt{n\log n}))=n^2/4+o(n^2)$, sampling method, approximate Carathéodory. Tablet note
1/2 Lecture 27: Khintchine inequality, approx function on abelian group, spectral sparsifier. Tablet note
1/6 Lecture 28: $\varepsilon$-net theorem via random samples. Tablet note