| Instructor | Kuan Yang |
|---|---|
| Lecture times | Tuesday 12:55 - 15:40 (Week 1 - 16) |
| Location | East Lower Hall 111 (东下院 111) |
| Teaching assistant(s) | Weihao Zhu (朱玮昊) |
| Office hours | Thursday 14:00 - 16:00 at Room 1402, School of Software |
12/01 Homework 7 announced, deadline: Dec. 14.11/09 Homework 6 announced, deadline: Nov. 18.10/28 Homework 5 announced, deadline: Nov. 4.10/20 Homework 4 announced, deadline: Oct. 28.10/13 Homework 3 announced, deadline: Oct. 21.09/30 Homework 2 announced, deadline: Oct. 14.09/23 Homework 1 announced, deadline: Sept. 30.
Extremal Combinatorics (With Applications in Computer Science) by Stasys Jukna, Springer.
The Probabilistic Method, 4th Edition by Noga Alon and Joel H. Spencer, Wiley.
Linear Algebra Methods in Combinatorics by László Babai and Péter Frankl, online.
Polynomial Methods in Combinatorics by Larry Guth, American Mathematical Society.
Polynomial Method in Combinatorics at Oxford
| Week | Date | Topics | Lecture notes | Homework |
|---|---|---|---|---|
| 1 | 09/13 | Introduction to the course, pigeonhole principle, Ramsey theory | Lecture 01 / manuscript | |
| 2 | 09/20 | Ramsey cont'd, double counting, Sperner's lemma and cake cutting, forbidden -cycle and forbidden | Lecture 02 / manuscript | HW1 |
| 3 | 09/27 | Introduction to the probabilistic method | Lecture 03 / manuscript | HW2 |
| 4 | 10/08 | Linearity of expectation, applications to incidence geometry, extremal set systems, Turán's theorem revisit | Lecture 04 / manuscript | |
| 5 | 10/11 | Alteration, second moment method, Weierstrass' approximation theorem | Lecture 05 / manuscript | HW3 |
| 6 | 10/18 | Thresholds of graph properties | Lecture 06 / manuscript | HW4 |
| 7 | 10/25 | Clique and chromatic number in , martingale concentration, Chernoff bound, Lovász local lemma | Lecture 07 / manuscript | HW5 |
| 8 | 11/01 | Local lemma, Moser-Tardos algorithm | Lecture 08 / manuscript | |
| 9 | 11/08 | Moser's original proof, entropy function | Lecture 09 / manuscript | HW6 |
| 10 | 11/15 | Shannon's source coding theorem, Szemerédi's regularity lemma | Lecture 10 / manuscript | |
| 11 | 11/22 | Application of regularity lemma, introduction to container method | Lecture 11 / manuscript | |
| 12 | 11/29 | Basic algebraic method, intersecting set family, graph decomposition | Lecture 12 / manuscript | HW7 |
| 13 | 12/06 | Eigenvalues of graphs, friendship theorem, Petersen graph, Moore graph | Lecture 13 / manuscript | |
| 14 | 12/13 | Polynomial method, Schwartz-Zippel lemma, finite field Kakeya problem | Lecture 14 / manuscript | HW8 |
| 15 | 12/20 | Combinatorial Nullstellensatz | Lecture 15 / manuscript | |
| 16 | 12/27 | Error correcting codes, list decoding, sensitivity conjecture, interlacing theorem | Lecture 16 / manuscript |