Teaching – Hong Liu 刘鸿

Spring 2024 Extremal Combinatorics

Spring 2024

Autumn 2022

Summer 2022

Spring 2022

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

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

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

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

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

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

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.

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.

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.

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.

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