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!

Part 1, Turán problem

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

•   Lecture 5. (Mar 30) Regularity lemma setup Tablet note Video Note 5
  
•   Lecture 6. (Apr 8) Reduced graph, embedding lemma, counting lemma, triangle removal lemma Tablet note Video 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.
  
•   Lecture 7. (Apr 13) (6,3)-thm, Roth's thm, induced matchings, Ramsey-Turán for K_4 Tablet note Video Note 7
  
•   Lecture 8. (Apr 20) linear Ramsey number for bounded degree graphs, spectral proof of the regularity lemma Tablet note Video Note 8
      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 Tablet note Video Note 9
  
•   Lecture 10. (May 11) Erdős-Ko-Rado, applications of (skewed) set-pairs inequalities to counting maximal uniform intersecting families and fractional Helly Tablet note Video Note 10
      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 Tablet note Video Note 11
  
•   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 Tablet note Video Note 12
      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 Tablet note Video Note 13
  
•   Lecture 14. (Jun 8) Complex Bollobás-Erdős graphsTablet note Video Note 14
      HW7: Prob 1, 2, 3 in (AS) Ch7.
  

Part 5, Container theorem

•   Lecture 15. (Jun 15) Kleitman-Winston graph container theorem, application to counting intersecting families Tablet note Video Note 15
  
•   Lecture 16. (Jun 22) Hypergraph container, count maximal triangle-free graphsTablet note Video Note 16
  

Lecture Notes by JK.

•   Lecture 1. (Mar 4) Random construction diagonal Ramsey, Tournament S_k property, Erdős-Ko-Rado Katona pf Video
•   Lecture 2. (Mar 11) hypergraph property B, size of sum-free sets, defn random variable, expectation, linearity of expectation, max cut of graphs Video
•   Lecture 3. (Mar 18) Max cut continued, unbalancing lights Video
•   Lecture 4. (Mar 25) List chromatic number, alteration method: Ramsey number lower bd, domination number upper bd Video
•   Lecture 5. (Apr 1) graphs with large girth and large chromatic number, improved bounds on hypergraph property B Video
•   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 Video
•   Lecture 7. (Apr 15) Binomial random graph model, Probability threshold for the appearance of a given balanced graph in random graph Video
•   Lecture 8. (Apr 22) Pippenger's theorem on hypergraph matching (Rödl nibble) Video
•   Lecture 9. (Apr 29) Pippenger's theorem on hypergraph matching (Rödl nibble), Lovász local lemma, lower bound on the diagonal Ramsey Video
•   Lecture 10. (May 13) Proof of the local lemma, lower bound on off-diagonal ramsey number R(3,k) using local lemma Video
•   Lecture 11. (May 20) Bounds on the linear arboricity using the local lemma Video
•   Lecture 12. (May 27) Lopsided local lemma, Moser’s fix-it algorithm. The four functions theorem Video
•   Lecture 13. (Jun 3) FKG inequality, Definition of martingales, examples of martingales Video
•   Lecture 14. (Jun 10) Azuma's inequality, Lipschitz condition Video
•   Lecture 15. (Jun 17) Clique number of random graphs, chromatic number of random graphs Video
•   Lecture 16. (Jun 24) Talagrand's inequality, concentration around the median Video