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

- Pigeonhole principle and Ramsey theory
- Double counting: forbidden -cycles and Sperner's lemma
- Forbidden subgraphs: Turán's theorem and Erdős–Stone-Simonovits theorem

- Basic techniques; linearity of expectation; alteration
- Second moment method; concentration of measures
- Lovász local lemma and Moser-Tardos algorithm
- Szemerédi's regularity lemma
- Container method

- Intersection of sets; odd town and even town
- Polynomial method: Schwartz–Zippel lemma, finite field Kakeya problem, etc
- Combinatorial Nullstellensatz
- Error-detecting codes and list-decoding

- Cauchy’s interlace theorem and sensitivity conjecture
- Intersecting set systems and Erdős-Rado sunflower conjecture

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 |