18.211 Fall 2020

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 (S3)

Disability and Access Services

“How to get help” flowchart

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?).

Find your homework partners

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