Math 566: Combinatorial Theory

Winter 2017

Course meets: Tuesday and Thursday 1:10-2:30 in 4096 East Hall.

Instructor: Sergey Fomin, 4868 East Hall, 764-6297,

Office hours: Tuesday and Thursday 2:40-4:00 in 4868 East Hall.

Grader: Qingzhong Liang,

Course homepage:

Level: introductory graduate/advanced undergraduate.

Prerequisites: Familiarity with formal proofs, and with basic notions of combinatorics. Linear algebra will be used throughout.

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. The text of this book (without exercises) is available at the link above.

Topics covered (tentative list, subject to change):


  • Graph eigenvalues
  • Enumeration of walks
  • Domino tilings
  • Random spanning trees
  • Resistor networks
  • Matrix-tree theorem
  • Cayley's Theorem
  • Eulerian tours
  • De Bruijn Sequences


  • Partitions and Young diagrams
  • Pentagonal Number Theorem
  • q-binomial coefficients
  • Sperner's theorem
  • Unimodality of Gaussian coefficients
  • Hooklength formula
  • Schensted correspondence
  • Tableaux and involutions
  • Knuth equivalence and Greene's theorem