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)

  20. Wed, March 20. q-analogs. Notes (pages 1-5)

  21. Fri, March 22. Gaussian q-binomial coefficients and Grassmannians over finite fields. Notes (pages 6-14)

    March 25-29: Spring break.

  22. Mon, Apr 1. Theory of partitions. Euler's theorem on odd and distinct partitions. Notes (pages 1-7)

  23. Wed, Apr 3. Theory of partitions (cont'd). Euler's pentagonal number theorem. Franklin's proof of pentagonal theorem. Involution principle. Notes (pages 8-15)

  24. Fri, Apr 5. Partition theory (cont'd). Jacobi's triple product formula. Notes (pages 1-9)

  25. Mon, Apr 8. Counting labelled trees. Cayley's formula. Notes (pages 1-10)

  26. Wed, Apr 10. Two bijective proofs of Cayley's formula: Prufer's coding and Egecioglu-Remmel bijection. Notes (pages 10-14) and Notes (pages 1-7)

  27. Fri, Apr 12. Spanning trees in graphs. Adjacency matrix. Incidence matrix. Laplacian matrix. Kirchhoff's Matrix Tree Theorem. Notes (pages 8-15)

  28. Wed, Apr 17. Proof of the Matrix Tree Theorem. Oriented incidence matrix. Cauchy-Binet formula. Notes (pages 1-10).

  29. Fri, Apr 19. Spectral graph theory. Products of graphs. Spanning trees in the hypercube graph. Notes (pages 1-9)

  30. Mon, Apr 22. Reciprocity formula for spanning trees. Notes (pages 1-4)

  31. Wed, Apr 24. Weighted and directed versions of matrix tree theorem. Counting arborescences. Notes (pages 5-15) and Notes (pages 1-5).

  32. Fri, Apr, 26. Electrical networks. Effective resistance and spanning trees. Notes

  33. Mon, Apr 29. Eulerian cycles in digraphs. B.E.S.T. Theorem. Notes (pages 3-14)

  34. Wed, May 1. Random walks on graphs. Probability = potential. Notes (pages 6-11).

  35. Fri, May 3. Parking functions. Notes (pages 1-10)

  36. Mon, May 6. Tree inversion polynomials and parking functions. Alternating permutations. Notes

  37. Wed, May 8. The chip firing game and the abelian sandpile model. Notes

  38. Fri, May 10. The abelian sandpile model (cont'd). The sandpile group of a graph. Notes

  39. Mon, May 13. Domino tilings and perfect matchings. Kasteleyn's and Temperley's theorems. Notes

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:   May 13, 2024