Math 565: Combinatorics and Graph Theory

Fall 2000

Course meets: MWF 2:10-3, 4096 East Hall.

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

Office hours: MWF 12-1 in 2858 East Hall (and by appointment).

Course homepage:

Level: introductory graduate/advanced undergraduate.

Prerequisites: No prior knowledge of combinatorics will be assumed. Basic algebra (mostly linear; Math 512/513 or equivalent) will be used throughout.

Student work expected: several problem sets.

Synopsis: The ultimate fun course, with a focus on problem solving, showcasing the gems of enumerative and algebraic combinatorics. The course will cover over a dozen of virtually independent topics, chosen solely on the basis of their beauty. Topics will include generating functions, algebraic graph theory, partially ordered sets, combinatorics of polytopes, matching theory, enumeration of tilings, partitions, and Young tableaux.

Topics covered:


  • 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.

This course has substantial overlap with Math 192 at Harvard, taught by Richard Stanley (M.I.T.).

Homework assignments: #1, #2. #3.