Math 566: Combinatorial Theory
(Algebraic and Enumerative Combinatorics)

Winter 2025

Course meets: Tuesday and Thursday 11:30-12:50 in 3096 East Hall.

Instructor: Sergey Fomin, 4868 East Hall, 764-6297, fomin@umich.edu

Office hours: Tuesday and Friday 1:00-2:20 in 4868 East Hall.

Grader: Yuchong Zhang, zongxun@umich.edu.

Course homepage: https://websites.umich.edu/~fomin/566w25.html

Level: introductory graduate/advanced undergraduate.

Prerequisites: Familiarity with formal proofs, basic notions of combinatorics, and advanced linear algebra.

Student work expected: several problem sets.

Synopsis: This course is an introduction to algebraic and enumerative combinatorics at the beginning graduate level. Topics include: fundamentals of algebraic graph theory; applications of linear algebra to enumeration of matchings, tilings, and spanning trees; combinatorics of electric networks; partially ordered sets; integer partitions and Young tableaux.

Optional text: R. P. Stanley, Algebraic Combinatorics: Walks, Trees, Tableaux, and More, Springer, 2013/2018.

Tentative list of topics:

  1. Graph eigenvalues. Counting walks.
  2. Eigenvalues of trees and circulant graphs.
  3. Eigenvalues of Cartesian products of graphs. Walks in a cube.
  4. Domino tilings. The permanent-determinant method.
  5. Tilings and spanning trees of planar graphs.
  6. The Diamond Lemma for terminating games.
  7. Additional applications and variations of the Diamond Lemma.
  8. Loop-erased walks. Cycle popping. Wilson’s algorithm.
  9. Flows. Resistor networks. Potentials. The Maximum Principle.
  10. Flows and potentials from random walks. Effective conductance.
  11. Effective conductance via spanning trees. Squaring the rectangle.
  12. Laplace expansion. Binet-Cauchy formula. Incidence matrix.
  13. Discrete Laplacian. Matrix-tree theorem. Spanning trees in regular graphs.
  14. Cayley's formula. Eulerian tours. The BEST theorem.
  15. Postman routes. De Bruijn sequences.
  16. Integer partitions. Generating functions for partitions.
  17. The pentagonal number theorem. The dominance order.
  18. The lattices L(m,n). The q-binomial coefficients.
  19. Identities for q-binomial coefficients.
  20. Sperner's theorem. Symmetric chain decompositions.
  21. Guest lecture: Prüfer codes. Parking functions.
  22. Unimodality of L(m,n).
  23. Proof of the Sperner property for L(m,n).
  24. Young tableaux. The hooklength formula.
  25. Proof of the hooklength formula.
  26. The Frobenius-Young identity.
  27. Tableaux and involutions.
  28. The Schensted correspondence.