Math 566: Combinatorial Theory

Winter 2003

Course meets: 3088 East Hall, TuTh 1:10-2:30.

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

Office hours: TuTh 2:30-3:30 in 2858 East Hall.

Grader: Greg Blekherman,

Course homepage:

Level: introductory graduate/advanced undergraduate.

Prerequisites: No prior knowledge of combinatorics will be assumed. Linear algebra will be used throughout.

Student work expected: several problem sets.

Textbook: none.

Synopsis: Introductory topics in algebraic combinatorics.

Topics covered (tentative, subject to change):


  • Cayley's Theorem.
  • Parking functions. The Shi arrangement.
  • Increasing trees.
  • Spectra of graphs
  • Counting walks
  • Domino tilings
  • The diamond lemma
  • Wilson's algorithm
  • Electric networks
  • Matrix-tree theorem
  • Eulerian tours
  • De Bruijn Sequences
  • Squaring the square


  • Partitions. Pentagonal Theorem
  • Dominance order
  • Bruhat order of the Grassmannian
  • q-binomial coefficients
  • Sperner's theorem
  • Distributive lattices
  • Unimodality of Gaussian coefficients
  • Hooklength formula
  • The Young lattice
  • Tableaux and involutions
  • Fibonacci lattices
  • The Schensted correspondence
  • Nilpotent varieties

Reference texts (none required):

M.Aigner and G.Ziegler, Proofs from The Book, Springer-Verlag, 2001.
A.Björner and R.P.Stanley, A combinatorial miscellany, Cambridge University Press, to appear.
B.Bollobas, Modern graph theory, Springer-Verlag, 1998.
I.Gessel and R.P.Stanley, Algebraic enumeration, in Handbook of Combinatorics, MIT Press, 1995.
J.H. van Lint and R.M.Wilson, A course in combinatorics , 2nd edition, Cambridge University Press, 2001.
R.P.Stanley, Enumerative combinatorics, vol.1-2, Cambridge University Press, 1997-1999.
Homework assignments: #1, #2, #3, #4, #5, #6.