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%
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