Autumn 2024 Extremal Combinatorics II. Methods
Spring 2024 Extremal Combinatorics I. Topics
Topics in Extremal Combinatorics
Convexity space
Discrete geometry
Topics 2
Part 1. Gibbs point process
- Shearer’s bound on independent number of triangle-free graphs, uniform sampling Tablet note
- Hard-core distribution, partition function, occupancy fraction, spacial Markov property Tablet note
- Independent number of triangle-free graphs, sampling with hard-core distribution Tablet note
- Sphere packing density, hard-sphere model Tablet note
- Improved bound on expected sphere packing density Tablet note
- Improved bound on expected sphere packing density 2 Tablet note
- Maximise occupancy fraction and number of independent sets among regular graphs Tablet note
Part 2. Polynomial methods
- Schwartz-Zippel lemma, polynomial identity testing and perfect matching testing Tablet note
- Discrete Kakeya set is dense, Dvir’s proof and Bukh-Chao’s tight bound Tablet note
- Joints theorem Tablet note
- Capset problem and slice rank of hypermatrices Tablet note
- Capset is exponentially small, Erdős-Szemerédi sunflower conjecture Tablet note
- Combinatorial Nullstellensatz, Cauchy-Davenport Tablet note
- Covering hypercube with affine hyperplanes, Chevalley-Warning, finding regular subgraphs, permanent lemma, Erdős-Ginzburg-Ziv Tablet note
Part 3. Pseudorandomness
- Quasirandom graphs, induced subgraph counts, subgraph counts, 4-cycle counts, spectral gap, discrepancy, codegree Tablet note
- Codegree implies induced subgraph counts Tablet note
- Expander mixing lemma, discrepancy implies codegree Tablet note
- Caylay graphs and their eigenvalues, characters of abelian groups, convolutions of two functions Tablet note
- Equivalence of discrepancy and spectral gap for Caylay graphs Tablet note
- Quasirandom sets in cyclic group, quasirandom 3-uniform hypergraph, quadratic uniformity Tablet note
Part 4. Spectral methods
- Spectral theorem, Hoffman’s bound on indepdence number, Rayleigh quotient, Courant-Fischer Tablet note
- Laplacian, Hoffman’s bound for irregular graphs, quadratic form defined by Laplacian and cuts of graphs Tablet note
- Spectrum of normalised Laplacian, eigenvalues of Laplacian of complete graphs, stars and hypercubes Tablet note
- Isoperimetric number, Cheeger constant, spectral gap defines expander Tablet note
- Conductance, Fiedler’s algorithm, Trevisan’s proof of Cheeger’s inequality Tablet note
- Robust Cheeger: bound conductance of a cut by Rayleigh quotient, Harper’s Isoperimetric inequality for hypercube, normalised Laplacian Tablet note
- Perron-Frobenius, random walk, transition matrix, stationary distribution Tablet note
- Spectrum of transition matrix, random walk on connected non-bipartite graph converges, mixing rate Tablet note
- Total variation distance, mixing time and conductance, random walk on expanders mixes fast and resembles independent sampling Tablet note
Part 5. Concentration of measure
- Chernoff, Azuma-Hoeffding, McDiarmid’s inequality, deviation inequality for slice of Boolean cube Tablet note
- Deviation inequality for slice of Hamming cube, application to sufficient conditions for small intersection of balls Tablet note
- Exponential decay of intersection in Hamming space, application on improvement of Gilbert-Varshamov bound for q-ary codes Tablet note
- Dimensionality reduction, Johnson-Lindenstrauss lemma Tablet note
- Subspace embedding, least square regression Tablet note
Entropy method
- Definition of entropy, entropy axioms à la Shannon-Khinchin, independence, non-negativity, monotonicity. Tablet note
- Chain rule, subadditivity, Shearer’s lemma, Loomis-Whitney inequality, entropy function satisfies axioms. Tablet note
- Summary of basic properties, volume of Hamming balls, triangle maximisation, triangle-intersecting family, entropy of uniform distribution. Tablet note
- Axioms determine entropy function uniquely, Brégman’s theorem on permanent of 0,1-matrices, Sidorenko’s conjecture for star of size 2. Tablet note
- Sidorenko’s conjecture for bipartite graphs with a dominating vertex, H-colourings. Tablet note
- Independent sets in bipartite regular graphs, counting matroids. Tablet note
- Tao’s entropy proof for sunflower. Tablet note
Topics 1
Part 1. Turán problem
- Mantel, Turán thm, Erdős-Simonovits stability, Symmetrisation à la Motzkin-Straus Tablet note Note-1
- Erdős-Simonovits-Stone, stability method, C_4-free graphs and Sidon set, Kövari-Sós-Turán Tablet note Note-2
-HW1: Exer 1.4, 2.3, 2.4 in Note 1; Exer 3.4 in Note 2; Prob 1, 2, 4 in Alon-Spencer (AS) Ch1. - Even cycles from BFS, supersaturation, regularisation, cube, degeneracy Tablet note Note-3
- Random algebraic constructions, rational Turán exponent conjecture Tablet note Note-4
-HW2: Exer 1.8 in Note 3; Exer 3.5 in Note 4; Prob 1, 2, 5, 9 in (AS) Ch2.
Part 2. Szemerédi regularity lemma
- Regularity lemma setup Tablet note Note-5
- Reduced graph, embedding lemma, counting lemma, triangle removal lemma Tablet note Note-6
-HW3: Exer 2.8 in Note 5; Exer 1.3, 3.3 in Note 6; Prob 1, 2, 3, 4 in (AS) Ch3. - (6,3)-thm, Roth’s thm, induced matchings, Ramsey-Turán for K_4 Tablet note Note-7
- Linear Ramsey number for bounded degree graphs, spectral proof of the regularity lemma Tablet note Note-8
-HW4: Exer 3.3 in Note 7; Prob 1, 2, 4, 5 in (AS) Ch4.
Part 3. Extremal set theory
- Sperner’s thm, LYM, (skewed) Bollobás set-pairs inequalities, applications to Littlewood-Offord, saturation number Tablet note Note-9
- Erdős-Ko-Rado, applications of (skewed) set-pairs inequalities to counting maximal uniform intersecting families and fractional Helly Tablet note Note-10
HW5: Exer 3.3 in Note 9; Exer 1.2, 1.5 in Note 10; Prob 1, 2, 3 in (AS) Ch5. - Fractional Helly, Kruskal-Katona, shift/compression Tablet note Note-11
- Dimension argument, odd town even town, sets with two distinct distance, Frankl-Wilson on sets with restricted intersection, sets of unit vectors with no orthogonal pairs, Kahn-Kalai’s disproof of Borsuk’s conjecture Tablet note Note-12
-HW6: Fact 2.6 in Note 11; Prob 1, 2, 3 in (AS) Ch6.
Part 4. Geometric constructions
- Behrend’s 3-AP-free/Green’s corner-free construction, Erdős-Rothschild problem on books Tablet note Note-13
- Complex Bollobás-Erdős graphs Tablet note Note-14
-HW7: Prob 1, 2, 3 in (AS) Ch7.
Part 5. Container theorem
- Kleitman-Winston graph container theorem, application to counting intersecting families Tablet note Note-15
- Hypergraph container, count maximal triangle-free graphs Tablet note Note-16