18.212      Algebraic Combinatorics        MIT Spring 2024

Instructor: Alexander Postnikov

Time: Monday, Wednesday, Friday 1:00-2:00 pm

Place: ROOM 4-237.

Canvas: For announcements and problem set submissions: https://canvas.mit.edu/courses/24334

Description: Applications of algebra to combinatorics and vise versa. We will discuss enumeration methods, permutations, partitions, partially ordered sets and lattices, Young tableaux, graph theory, matrix tree theorem, electrical networks, random walks, convex polytopes, and other topics.

Course Level: Advanced Undergraduate.

Keywords: Catalan numbers, Dyck paths, triangulations, non-crossing set partitions, symmetric group, statistics on permutations, inversions and major index, partially ordered sets and lattices, Sperner's and Dilworth's theorems, Young diagrams, Young's lattice, Gaussian q-binomial coefficients, standard Young tableaux (STY), Robinson-Schensted-Knuth (RSK) correspondence, partitions, Euler's pentagonal theorem, Jacobi triple product, non-crossing paths, Lindstrom-Gessel-Viennot lemma, spanning trees, parking functions, Prufer codes, matrix-tree theorem, electrical networks, random walks on graphs, graph colorings, chromatic polynomial, Mobius function, continued fractions, enumeration under group action, Burnside's lemma, Polya theory, transportation and Birkhoff polytopes, cyclic polytopes, permutohedra, domino tilings, matching enumeration, Pfaffians, Ising model.

Grading: Based on several Problems Sets.

Problem Sets:

Lectures:

We include links to related lecture notes from previous years. The notes may contain some additional material not covered in the lectures.

  1. Mon, Feb 5. The Catalan numbers, Dyck paths, Bertrand's ballot problem, reflection method. Notes

  2. Wed, Feb 7. The Catalan numbers (cont'd): recurrence relation, generating function, generalized binomial coefficients, binary trees. Notes

  3. Fri, Feb 9. The Catalan numbers (cont'd): combinatorial interpretations (binary trees, plane trees, triangulations of polygons, non-crossing and non-nesting matchings, etc). Notes

  4. Mon, Feb 12. Integer partitions. Young diagrams and standard Young tableaux. The hook length formula. Notes (pages 1-7)

  5. Wed, Feb 14. Probabilistic "hook walk" proof of the hook length formula. Notes (pages 8-17)

  6. Fri, Feb 16. Set partitions. The Bell numbers and the Stirling numbers of the second kind. Rook placements. Notes (pages 1-11)

  7. Tue, Feb 20. Exponential generating functions. The exponential formula. Notes (pages 1-7)

  8. Wed, Feb 21. Applications of the exponential formula. Notes (pages 8-15)

  9. Fri, Feb 23. Cycles in permutations. The Stirling numbers of the first kind. The Stirling numbers (of both kinds) as coefficients in change of bases matrices. Recurrence relations for the Stirling numbers and their ``Pascal-like'' triangles. Notes (pages 16-21) and these Notes (pages 9-15)

  10. Mon, Feb 26. The Eulerian numbers and the Eulerian triangle. Notes (page 16)

  11. Wed, Feb 28. Statistics on permutations: inversions, descents, cycles, major index, records, exceedances. Notes (pages 1-8)

  12. Fri, March 1. Sperner's Theorem. Posets. Notes (pages 1-8).

  13. Mon, March 4. Rank unimodality and Sperner property of posets. Symmetric chain decompositions (SCD). Products of posets. Notes (pages 9-15)

  14. Wed March 6. Dilworth's, Mirsky's, and Greene's theorems for posets. Posets associated to permutations. Increasing and decreasing subsequences in permutations. Notes (pages 1-4)

  15. Fri March 8. Ramsey's and Erdos-Szekeres theorems. Graphs vs posets vs permutations. Young's lattice. Notes (page 7)

  16. Mon, March 11. The Robinson-Schensted-(Knuth) correspondence (RSK). Schensted's insertion algorithm. Increasing and descreasing subsequences in permutations. Notes (pages 1-7)

  17. Wed March 13. Symmetry of RSK. 321-avoiding permutations. Walks on Young's lattice. Notes (pages 8-9)

  18. Fri March 15. Oscillating tableaux and rook placements. Up and down operators on Young's lattice. Notes (pages 10-15)

  19. Mon, March 18. Differential posets. Hopping particles and anti-particles. The Young-Fibonacci lattice. Notes (pages 1-23)

Additional reading materials: (The students are not required to buy these books.)

[AC]  Algebraic Combinatorics: Walks, Trees, Tableaux, and More by R. P. Stanley, Springer.
Book info including Text of version of 2013 (without exercises), available at Richard Stanley's webpage.

[EC1] Enumerative Combinatorics Vol 1 by R. P. Stanley, Cambridge University Press.
Book info from Richard Stanley's webpage.

[18.212'2019] 18.212 Lecture Notes from 2019 (the notes are taken by Andrew Lin).

Last updated:   March 1, 2024