Math 565: Combinatorics and Graph Theory

Fall 2007

Course meets: Tuesday and Thursday 11:40-1:00 in 2866 East Hall.

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

Office hours: Tuesday 2:40-3:40 and Thursday 4:10-5:30 in 2858 East Hall.

Grader: Nina White,

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.

Synopsis: Applications of algebra (mostly linear algebra) to combinatorics. Topics include: algebraic graph theory; enumeration methods; matchings, tilings, and electric networks; posets, partitions, and tableaux. The course will emphasize problem solving (as opposed to theory-building).

Topics covered (tentative list, subject to change):


  • Cayley's Theorem
  • De Bruijn Sequences
  • Hooklength formula


  • Spectra of graphs
  • Walks on a cube
  • Sperner's theorem
  • Matrix-tree theorem
  • Eulerian tours
  • Domino tilings


  • Partitions. Pentagonal Number Theorem
  • Young's lattice
  • The Schensted correspondence
  • Tableaux and involutions


  • Catalan numbers
  • Stirling numbers
  • Inversions and major index
  • q-binomial coefficients
  • Rook polynomials
  • Polya theory


  • Theorems of P.Hall and G.König
  • Birkhoff's theorem. The assignment polytope
  • Cyclic polytopes
  • Permutohedra
  • The weak order of the symmetric group

Reference texts (none required):

A.Björner and R.P.Stanley, A combinatorial miscellany, Cambridge University Press, to appear.
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 , Cambridge University Press, 1996.
R.P.Stanley, Enumerative combinatorics, vol.1-2, Cambridge University Press, 1997-1999.