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:
- Graph eigenvalues. Counting walks.
- Inequalities for the maximal eigenvalue. Eigenvalues of bipartite graphs.
- Eigenvalues of circulant graphs. Eigenvalues of Cartesian products of graphs.
- Walks in a cube. Domino tilings.
- The permanent-determinant method. Domino tilings of a rectangle.
- Tilings and spanning trees of planar graphs. The Diamond Lemma for terminating games.
- Applications of the Diamond Lemma. The Diamond Lemma for non-terminating games.
- Loop-erased walks. Cycle popping. Wilson’s algorithm.
- Flows. Resistor networks.
- Potentials. The Maximum Principle. Flows from random walks.
- Electric networks and spanning trees. Effective conductance.
- Effective conductance via spanning trees. Squaring the rectangle.
- Laplace expansion. Binet-Cauchy formula. Incidence matrix.
- Discrete Laplacian. Matrix-tree theorem. Spanning trees in regular graphs.
- Cayley's formula. Eulerian tours. The BEST theorem.
- Postman routes. De Bruijn sequences.
- Integer partitions. Generating functions for partitions.
- The dominance order.
- The lattices L(m,n). The q-binomial coefficients.
- Identities for q-binomial coefficients.
- Sperner's theorem.
- Unimodality of L(m,n).
- Young tableaux. The hooklength formula.
- Proof of the hooklength formula.
- The Frobenius-Young identity.
- Tableaux and involutions.
- The Schensted correspondence.