Math 566: Combinatorial Theory
(Algebraic and Enumerative Combinatorics)

Winter 2022

Course meets: Tuesday and Thursday 11:30-12:50 in 4096 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: Yanjun Chen, yanjunc@umich.edu.

Course homepage: http://www.math.lsa.umich.edu/~fomin/566w22.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. The text of this book (without exercises) is available at the link above.

Topics covered:

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

Homework assignments: #1 (due 01/20), #2 (due 02/03), #3 (due 02/24), #4 (due 03/24), #5 (due 04/07), #6 (due 04/14).
Submit here via Gradescope.
On each problem set, completely solving all problems but two (without any mistakes) will constitute a 100% score.