CS3334: Advanced Combinatorics

Shanghai Jiao Tong University, Fall 2022


Course Information

InstructorKuan Yang
Lecture timesTuesday 12:55 - 15:40    (Week 1 - 16)
LocationEast Lower Hall 111 (东下院 111)
Teaching assistant(s)Weihao Zhu (朱玮昊)
Office hoursThursday 14:00 - 16:00 at Room 1402, School of Software

News and Announcements


Textbook and References


1. Basic topics in extremal graph theory
2. The probabilistic method
3. The linear algebra method
4. Highlights in recent years


Lecture Schedule

WeekDateTopicsLecture notesHomework
109/13Introduction to the course,
pigeonhole principle, Ramsey theory
Lecture 01 / manuscript 
209/20Ramsey cont'd, double counting,
Sperner's lemma and cake cutting,
forbidden -cycle and forbidden
Lecture 02 / manuscriptHW1
309/27Introduction to the probabilistic methodLecture 03 / manuscriptHW2
410/08Linearity of expectation, applications
to incidence geometry, extremal set
systems, Turán's theorem revisit
Lecture 04 / manuscript 
510/11Alteration, second moment method,
Weierstrass' approximation theorem
Lecture 05 / manuscriptHW3
610/18Thresholds of graph propertiesLecture 06 / manuscriptHW4
710/25Clique and chromatic number in
, martingale concentration,
Chernoff bound, Lovász local lemma
Lecture 07 / manuscriptHW5
811/01Local lemma, Moser-Tardos algorithmLecture 08 / manuscript 
911/08Moser's original proof, entropy functionLecture 09 / manuscriptHW6
1011/15Shannon's source coding theorem,
Szemerédi's regularity lemma
Lecture 10 / manuscript 
1111/22Application of regularity lemma,
introduction to container method
Lecture 11 / manuscript 
1211/29Basic algebraic method, intersecting
set family, graph decomposition
Lecture 12 / manuscriptHW7
1312/06Eigenvalues of graphs, friendship
theorem, Petersen graph, Moore graph
Lecture 13 / manuscript 
1412/13Polynomial method, Schwartz-Zippel
lemma, finite field Kakeya problem
Lecture 14 / manuscriptHW8
1512/20Combinatorial NullstellensatzLecture 15 / manuscript 
1612/27Error correcting codes, list decoding,
sensitivity conjecture, interlacing theorem
Lecture 16 / manuscript