HONG LIU   刘鸿

Topics in Combinatorics

Welcome to the webpage of the online course "Topics in Combinatorics" by Jaehoon Kim (JK) and Hong Liu (HL). We plan to cover some classical topics, methods and some recent development in extremal and probabilistic combinatorics and related areas.

•   Time:   Every Tuesday (HL) and Thursday (JK) Beijing time 3pm-4:30pm, 2 March - 24 June, 2021
•   Zoom ID:   827 7488 5737,   password: 202121
Announcement
•   No class on the first week of May!

Tuesdays schedule

Part 1, Turán problem

•   Lecture 1. (Mar 2) Mantel,Turán thm, Erdős-Simonovits stability, Symmetrisation à la Motzkin-Straus
•   Lecture 2. (Mar 9) Erdős-Simonovits-Stone, stability method, C_4-free graphs and Sidon set, Kövari-Sós-Turán
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.
•   Lecture 3. (Mar 16) Even cycles from BFS, supersaturation, regularisation, cube, degeneracy
•   Lecture 4. (Mar 23) Random algebraic constructions, rational Turán exponent conjecture
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

•   Lecture 5. (Mar 30) Regularity lemma setup
•   Lecture 6. (Apr 8) Reduced graph, embedding lemma, counting lemma, triangle removal lemma
HW3: Exer 2.8 in Note 5; Exer 1.3, 3.3 in Note 6; Prob 1, 2, 3, 4 in (AS) Ch3.
•   Lecture 7. (Apr 13) (6,3)-thm, Roth's thm, induced matchings, Ramsey-Turán for K_4
•   Lecture 8. (Apr 20) linear Ramsey number for bounded degree graphs, spectral proof of the regularity lemma
HW4: Exer 3.3 in Note 7; Prob 1, 2, 4, 5 in (AS) Ch4.

Part 3, Extremal set theory

•   Lecture 9. (Apr 27) Sperner's thm, LYM, (skewed) Bollobás set-pairs inequalities, applications to Littlewood-Offord, saturation number
•   Lecture 10. (May 11) Erdős-Ko-Rado, applications of (skewed) set-pairs inequalities to counting maximal uniform intersecting families and fractional Helly
HW5: Exer 3.3 in Note 9; Exer 1.2, 1.5 in Note 10; Prob 1, 2, 3 in (AS) Ch5.
•   Lecture 11. (May 18) Fractional Helly, Kruskal-Katona, shift/compression
•   Lecture 12. (May 25) 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
HW6: Fact 2.6 in Note 11; Prob 1, 2, 3 in (AS) Ch6.

Part 4, Geometric constructions

•   Lecture 13. (Jun 1) Behrend's 3-AP-free/Green's corner-free construction, Erdős-Rothschild problem on books
•   Lecture 14. (Jun 8) Complex Bollobás-Erdős graphs
HW7: ; Prob in (AS) Ch6.

Thursdays schedule

by JK.

•   Lecture 1. (Mar 4) Random construction diagonal Ramsey, Tournament S_k property, Erdős-Ko-Rado Katona pf
•   Lecture 2. (Mar 11) hypergraph property B, size of sum-free sets, defn random variable, expectation, linearity of expectation, max cut of graphs
•   Lecture 3. (Mar 18) Max cut continued, unbalancing lights
•   Lecture 4. (Mar 25) List chromatic number, alteration method: Ramsey number lower bd, domination number upper bd
•   Lecture 5. (Apr 1) graphs with large girth and large chromatic number, improved bounds on hypergraph property B
•   Lecture 6. (Apr 6) Dependent random choice, Turan number of bipartite graphs with maximum degree on one side bounded, the second moment method, bounds on the size of sets with distinct sums
•   Lecture 7. (Apr 15) Binomial random graph model, Probability threshold for the appearance of a given balanced graph in random graph
•   Lecture 8. (Apr 22) Pippenger's theorem on hypergraph matching (Rödl nibble)
•   Lecture 9. (Apr 29) Pippenger's theorem on hypergraph matching (Rödl nibble), Lovász local lemma, lower bound on the diagonal Ramsey
•   Lecture 10. (May 13) Proof of the local lemma, lower bound on off-diagonal ramsey number R(3,k) using local lemma
•   Lecture 11. (May 20) Bounds on the linear arboricity using the local lemma
•   Lecture 12. (May 27) Lopsided local lemma, Moser’s fix-it algorithm. The four functions theorem
•   Lecture 13. (Jun 3) FKG inequality, Definition of martingales, examples of martingales