**Fall 2020, Massachusetts Institute of ****Technology**

**Class meetings: **Mondays, Wednesdays and Fridays 11am–noon

**Instructor: **Zilin Jiang (he, him, his)

**Office hours:** Mondays 1pm–2pm and Tuesdays 3:30pm–4:30pm

**Teaching assistant: **Daniil Klieuev

**Course description**

Welcome to the land of combinatorics! In this guided tour, we will explore different concepts in combinatorics (also known as discrete creatures), and the connections thereof.

**Prerequisites:** Calculus II (GIR) and linear algebra (18.06 or 18.700 or 18.701). Prior experience with abstraction and proofs is helpful.

**Required textbook:** *Invitation to discrete mathematics* by Jiří Matoušek and Jaroslav Nešetřil [library]

**Onboarding:**

- Please fill out the pre-semester questionnaire.
- Read Chapter 1 in the textbook before classes start; we will spend little or no class time on these. Self-check by trying some exercises in these sections.
- Consider learning how to use LaTeX (I recommend the tutorials on Overleaf), although this is not required for this class.

**Resources:**

*Concrete mathematics*by Ronald Graham, Donald Knuth, and Oren Patashnik [library]*Enumerative combinatorics, volume I*by Richard Stanley [library]*Graph theory*by Reinhard Diestel [library]*Probabilistic method*by Noga Alon, and Joel Spencer [library].*Ramsey theory*by Ronald Graham, Bruce Rothschild, and Joel Spencer [library]*Generatingfunctionology*by Herbert Wilf [library] [online]*Analytic combinatorics*by Philippe Flajolet, and Robert Sedgewick [library] [online]*Thirty-three miniatures: mathematical and algorithmic applications of linear algebra*by Jiří Matoušek [library] [online]

**Asking questions:**

Math is easier to explain live, so for math questions it is best to come to office hours. Another possibility: Ask them on Piazza. Administrative questions too can be asked there, especially if other students might be able to answer them or might learn from the answer.

**Grading**

3 in-class midterms worth 20% each, and homework for the remaining 40%

Student Support Services (S^{3})

Disability and Access Services

**Midterms**

- 50 min in-class midterms.
- No notes and electronic devices (including calculators, phones, etc.) may be used.

**Homework**

Submissions may be either typed or legibly written. All steps should be justified. You are strongly encouraged to do as much homework as possible individually; you will gain the most of out the course this way.

*Sources and collaboration policy.* Collaboration and use of external sources are permitted, but must be fully acknowledged and cited. Collaboration may involve only discussion; all the writing must be done individually. Failure to do so will be treated as cheating (see What is Academic Integrity?).

*Late policy. *The homework must be submitted by *noon* of the day it is due. For each *hour* that it is late, the assignment grade will be reduced by 5%.

**Schedule**

**Week 1**

Sep 2. Class overview. Partial orderings and linear orderings.

Sep 4. Linearize a partial ordering. Embed into an ordering by inclusion.

**Week 2**

Sep 7. *No class (Labor Day)*

Sep 9. “Tall or wide” theorem. Erdős–Szekeres theorem. Basic counting.

Sep 11. Permutation. Factorial. Binomial Coefficients.

**Week 3**

Sep 14. Estimation, Stirling’s formula, inclusion-exclusion principle, derangements.

Sep 16. Graph isomorphism, connectedness, adjacency matrix.

Sep 18. Counting walks, handshake lemma, score theorem.

**Week 4**

Sep 21. Eulerian graph (undirected and directed) and an application.

Sep 23. Vertex connectivity, 2-connected graph synthesis

Sep 25. Turán’s theorem, trees and algorithms

**Week 5**

Sep 28. Planar graphs, Kuratowski’s theorem, drawing on a torus

Sep 30. **In-class midterm #1**

Oct 2. Euler’s formula, planar graph is sparse

**Week 6**

Oct 5. Dual graph, chromatic number, the 5-color theorem, Sperner’s lemma

Oct 7. Sperner’s theorem

Oct 9. Kővári–Sós–Turán theorem, Cayley’s formula

**Week 7**

Oct 12. *No class* (Columbus Day)

Oct 13 (Tuesday) *Monday schedule to be held. *Prüfer code, Kirchhoff’s matrix tree theorem, Cauchy–Binet formula

Oct 14. Basic properties of finite projective planes

Oct 16. Projective planes over finite fields, orthogonal Latin squares

**Week 8**

Oct 19. 2-colorability, finite probability space

Oct 21. Independent events, random variable, linearity of expectation

Oct 23. Probabilistic proof of Turán’s theorem, estimating intersections at level k

**Week 9**

Oct 26. Bounds on Ramsey number, Multi-color Ramsey, Schur’s theorem

Oct 28. **In-class midterm #2**

Oct 30. Fermat’s last theorem modulo primes, ordinary generating functions

**Week 10**

Nov 2. Manufacturing generation functions

Nov 4. Fibonacci numbers and homogeneous linear recursions

Nov 6. Homogeneous linear recurrences (cont.), Catalan numbers, generating function for random variables

**Week 11**

Nov 9. Random walk on R, integer partitions

Nov 11 *No class (Veterans Day)*

Nov 13. Block design, Steiner triple system, BIBD, William’s theorem, Keevash’s theorem

**Week 12**

Nov 16. Fisher’s inequality, Graham–Pollak theorem

Nov 18. Cycle space, circulation space, cut space

Nov 20. Freivalds’ matrix multiplication checker, associativity checker

**Week 13 ***No class* (Thanksgiving)

**Week 14**

Nov 30. Spectrum of a graph, Hoffman’s bound on independence number, Wilf’s bound on chromatic number

Dec 2. **In-class midterm #3**

Dec 4. Cauchy interlacing, Pseudo-adjacency matrix, Huang’s proof of sensitivity conjecture

**Week 15**

Dec 7. The Borsuk–Ulam theorem and its variants, triangle-free graphs with high chromatic number

Dec 9. Kneser’s conjecture, the necklace problem