18.212      Algebraic Combinatorics        MIT Spring 2025

Instructor: Alexander Postnikov (office hour: Monday 2 pm, Room 2-367)

TA: Ilani Axelrod-Freed (office hour: Friday 3 pm, Room 2-390c)

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

Where: Room 4-237

Canvas: https://canvas-mit-edu.ezproxyberklee.flo.org/courses/30095

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:

Lecture Notes:

Lecture Notes by Marvin Mao.

Lecture Notes by Davit Kldiashvili.

Lecture Notes from 2021

Lecture Notes from 2019 by Andrew Lin.

Lectures: (with links to addional reading materials)

  1. Mon, Feb 3. The Catalan numbers C_n. Dyck paths, triangulations, parenthesizations, binary trees, and non-crossing matchings. Some bijections.

  2. Wed, Feb 5. The Catalan numbers (cont'd). More bijections. Proof of the formula for C_n using reflection method.

  3. Fri, Feb 7. The Catalan numbers (cont'd). Proof of the formula for C_n using cyclic shifts. Stack-sorting and queue-sorting of permutations. 321-avoiding and 231-avoiding permutations.

  4. Mon, Feb 10. Young tableaux. The Hook Length Formula (HLF) for Standard Young Tableaux (SYT).

  5. Wed, Feb 12. A probabilistic ``Hook Walk'' proof of the HLF by Greene, Nijenhuis, Wilf.

  6. Fri, Feb 14. Permutations: 1-line notation, 2-line notation, graphical notation, cycle notation. Statisticls on permutations: inv, des, cyc, maj, rec, exc, aexc, wexc. Equidistributed statistics.

  7. Tue, Feb 18. (Lecture by Ilani Axelrod-Freed) Robinson-Schensted correspondence (RSK). Schensted insertion algorithm. Greene's theorem.

  8. Wed, Feb 19. The Eulerian numbers A(n,k). Euler's computation of some infinite power series. Combinatorial interpretations of the Eulerian numbers in terms of descents and exceedances. The Eulerian triangle.

  9. Fri, Feb 21. The Stirling numbers of two kinds s(n,k) and S(n,k). Two Stirling triangles. Falling factorials. Stirling numbers are matrix elements of change-of-basis matrices.

  10. Mon, Feb 24. Sperner's theorem. Partially ordered sets (posets). Chains and antichains in posets.

  11. Wed, Feb 26. Symmetric chain decompositions (SCD). Proofs of Sperner's and de Bruijn's theorems. Dilworth's and Mirsky's theorems.

  12. Fri, Feb 28. Problem Set 1 is due! Submit your solutions here.

Textbooks: Many (but not all) topics that we dicuss in class can be found in these books. The students are not required to buy these books. However, it is good idea to take a look at them.

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

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

Last updated:   Feb 28, 2025