Topics in Combinatorics 2

Welcome to the webpage of the online course "Topics in Combinatorics 2". We continue to cover some classical topics, methods and some recent development in extremal and probabilistic combinatorics and related areas.

•   Latex Notes will be updated within a week after each class.
•   Time:   Every Tuesday and Thursday Beijing time 8:30am-9:30am, Sep 7 - Dec 28, 2021
•   Zoom ID:   840 8408 4311,   password: 202121
•   QQ Group:   794 588 327

Announcement

•   No class on Tuesday Sep 21 (中秋快乐)!

•   Lecture 1. (Sep 7) Shearer's bound on independent number of triangle-free graphs, uniform sampling  Tablet note Video
  
•   Lecture 2. (Sep 9) Hard-core distribution, partition function, occupancy fraction, spacial Markov property  Tablet note Video
  
•   Lecture 3. (Sep 14) Independent number of triangle-free graphs, sampling with hard-core distribution  Tablet note Video
  
•   Lecture 4. (Sep 16) Sphere packing density, hard-sphere model  Tablet note Video
  
•   Lecture 5. (Sep 23) Improved bound on expected sphere packing density  Tablet note Video
  
•   Lecture 6. (Sep 28) Improved bound on expected sphere packing density 2  Tablet note Video
  
•   Lecture 7. (Sep 30) Maximise occupancy fraction and number of independent sets among regular graphs  Tablet note Video
  

•   Lecture 8. (Oct 5) Schwartz-Zippel lemma, polynomial identity testing and perfect matching testing  Tablet note Video
  
•   Lecture 9. (Oct 7) Discrete Kakeya set is dense, Dvir's proof and Bukh-Chao's tight bound  Tablet note Video
  
•   Lecture 10. (Oct 12) Joints theorem  Tablet note Video
  
•   Lecture 11. (Oct 14) Capset problem and slice rank of hypermatrices  Tablet note Video
  
•   Lecture 12. (Oct 19) Capset is exponentially small, Erdős-Szemerédi sunflower conjecture  Tablet note Video
  
•   Lecture 13. (Oct 21) Combinatorial Nullstellensatz, Cauchy-Davenport  Tablet note Video
  
•   Lecture 14. (Oct 26) Covering hypercube with affine hyperplanes, Chevalley-Warning, finding regular subgraphs, permanent lemma, Erdős-Ginzburg-Ziv  Tablet note Video
  

•   Lecture 15. (Oct 28) Quasirandom graphs, induced subgraph counts, subgraph counts, 4-cycle counts, spectral gap, discrepancy, codegree  Tablet note Video
  
•   Lecture 16. (Nov 2) Codegree implies induced subgraph counts  Tablet note Video
  
•   Lecture 17. (Nov 4) Expander mixing lemma, discrepancy implies codegree  Tablet note Video
  
•   Lecture 18. (Nov 9) Caylay graphs and their eigenvalues, characters of abelian groups, convolutions of two functions  Tablet note Video
  
•   Lecture 19. (Nov 11) Equivalence of discrepancy and spectral gap for Caylay graphs  Tablet note Video
  
•   Lecture 20. (Nov 16) Quasirandom sets in cyclic group, quasirandom 3-uniform hypergraph, quadratic uniformity  Tablet note Video
  

•   Lecture 21. (Nov 18) Spectral theorem, Hoffman's bound on indepdence number, Rayleigh quotient, Courant-Fischer  Tablet note Video
  
•   Lecture 22. (Nov 23) Laplacian, Hoffman's bound for irregular graphs, quadratic form defined by Laplacian and cuts of graphs  Tablet note Video
  
•   Lecture 23. (Nov 25) Spectrum of normalised Laplacian, eigenvalues of Laplacian of complete graphs, stars and hypercubes  Tablet note Video
  
•   Lecture 24. (Nov 30) Isoperimetric number, Cheeger constant, spectral gap defines expander  Tablet note Video
  
•   Lecture 25. (Dec 2) Conductance, Fiedler's algorithm, Trevisan's proof of Cheeger's inequality  Tablet note Video
  
•   Lecture 26. (Dec 7) Robust Cheeger: bound conductance of a cut by Rayleigh quotient, Harper's Isoperimetric inequality for hypercube, normalised Laplacian  Tablet note Video
  
•   Lecture 27. (Dec 9) Perron-Frobenius, random walk, transition matrix, stationary distribution  Tablet note Video
  
•   Lecture 28. (Dec 14) Spectrum of transition matrix, random walk on connected non-bipartite graph converges, mixing rate  Tablet note Video
  
•   Lecture 29. (Dec 16) total variation distance, mixing time and conductance, random walk on expanders mixes fast and resembles independent sampling  Tablet note Video
  

•   Lecture 30. (Dec 23) Chernoff, Azuma-Hoeffding, McDiarmid's inequality, deviation inequality for slice of Boolean cube  Tablet note Video
  
•   Lecture 31. (Dec 28) deviation inequality for slice of Hamming cube, application to sufficient conditions for small intersection of balls  Tablet note Video
  
•   Lecture 32. (Dec 30) Exponential decay of intersection in Hamming space, application on improvement of Gilbert-Varshamov bound for q-ary codes  Tablet note Video
  
•   Lecture 33. (Jan 4) Dimensionality reduction, Johnson-Lindenstrauss lemma  Tablet note Video
  
•   Lecture 34. (Jan 6) Subspace embedding, least square regression  Tablet note Video