Course meets: Tuesdays and Thursdays, 1-2:30,
Room 2-142.
Lecturer: Professor
Sergey Fomin,
Room 2-363B, 253-1713,
fomin@math.mit.edu
Office hours: Wednesday, 12:30-2 p.m. (and by appointment).
Teaching assistant: Adrian Vetta,
Room 2-342,
avetta@math.mit.edu
Text:
van Lint and Wilson, A Course in Combinatorics,
Cambridge University Press, 1996
(selected chapters).
Course homepage: http://www-math.mit.edu/~fomin/18312.html
Course description from the MIT Catalog
Applications of algebra to combinatorics and conversely. Topics include enumeration methods, partially
ordered sets and lattices, matching theory and extremal set theory, partitions, tilings, codes, and designs.
No prior knowledge of combinatorics is assumed, though 18.314 is helpful.
Prerequisites: 18.700 or 18.701.
Level: advanced undergraduate.
Past lectures
1. Hooklength formula.
2. De Bruijn sequences.
3. Enumeration of trees.
4. Stirling numbers.
5. Spectra of graphs.
6. Walks on a cube.
7. Sperner's theorem.
8. Symmetric chain decompositions.
9. Inversions and major index.
10. q-binomial coefficients.
11. Distributive lattices.
12. Gaussian coefficients.
13. Tableaux and involutions.
14. Schensted's correspondence.
15-16. Catalan numbers.
17. Matrix-tree theorem.
18. Eulerian tours.
19-20. Domino tilings.
21. Burnside's lemma.
22. Polya theory.
23. The marriage theorem.
24. Assignment polytope.
25. Cyclic polytopes.
26. Permutohedra.
Homework assignments
Problem Set 1, due 9/25
Problem Set 2, due 10/16
Problem Set 3, due 11/6
Problem Set 4, due 12/4