Math 566: Combinatorial Theory
Winter 2003
Course meets: 3088 East Hall, TuTh 1:102:30.
Instructor:
Sergey Fomin, 2858 East Hall, 7646297,
fomin@umich.edu
Office hours: TuTh 2:303:30 in 2858 East Hall.
Grader: Greg Blekherman, gblekher@umich.edu.
Course homepage: http://www.math.lsa.umich.edu/~fomin/566.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.
Textbook: none.
Synopsis:
Introductory topics in algebraic combinatorics.
Topics covered (tentative, subject to change):
GRAPHS AND TREES
 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
 Matrixtree theorem
 Eulerian tours
 De Bruijn Sequences
 Squaring the square
POSETS AND PARTITIONS
 Partitions. Pentagonal Theorem
 Dominance order
 Bruhat order of the Grassmannian
 qbinomial 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):
 [AZ]
 M.Aigner and G.Ziegler, Proofs from The Book,
SpringerVerlag, 2001.
 [BS]
 A.Björner and R.P.Stanley, A combinatorial miscellany,
Cambridge University Press, to appear.
 [B]
 B.Bollobas, Modern graph theory,
SpringerVerlag, 1998.
 [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 , 2nd edition, Cambridge University Press,
2001.
 [EC]

R.P.Stanley,
Enumerative combinatorics, vol.12,
Cambridge University Press, 19971999.
Homework assignments:
#1,
#2,
#3,
#4,
#5,
#6.