Math 565: Combinatorics and Graph Theory
Fall 2007
Course meets: Tuesday and Thursday 11:401:00 in 2866 East Hall.
Instructor:
Sergey Fomin, 2858 East Hall, 7646297,
fomin@umich.edu
Office hours: Tuesday 2:403:40 and Thursday 4:105:30 in 2858 East Hall.
Grader:
Nina White,
whitenj@umich.edu.
Course homepage: http://www.math.lsa.umich.edu/~fomin/565f07.html
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 theorybuilding).
Topics covered (tentative list, subject to change):
INTRODUCTION
 Cayley's Theorem
 De Bruijn Sequences
 Hooklength formula
ALGEBRAIC GRAPH THEORY
 Spectra of graphs
 Walks on a cube
 Sperner's theorem
 Matrixtree theorem
 Eulerian tours
 Domino tilings
PARTITIONS AND TABLEAUX
 Partitions. Pentagonal Number Theorem
 Young's lattice
 The Schensted correspondence
 Tableaux and involutions
CLASSICAL ENUMERATION
 Catalan numbers
 Stirling numbers
 Inversions and major index
 qbinomial coefficients
 Rook polynomials
 Polya theory
DISCRETE GEOMETRY
 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):
 [BS]
 A.Björner and R.P.Stanley, A combinatorial miscellany,
Cambridge University Press, to appear.
 [GS]
 I.Gessel and R.P.Stanley, Algebraic enumeration,
in Handbook of Combinatorics, MIT Press, 1995.
 [vW]
 J.H. van Lint and R.M.Wilson, A course in combinatorics , Cambridge University Press,
1996.
 [EC]

R.P.Stanley,
Enumerative combinatorics, vol.12,
Cambridge University Press, 19971999.