Math 566: Combinatorial Theory

Winter 2003

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

Instructor: Sergey Fomin, 2858 East Hall, 764-6297, fomin@umich.edu

Office hours: TuTh 2:30-3: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 Matrix-tree theorem Eulerian tours De Bruijn Sequences Squaring the square POSETS AND PARTITIONS 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):

[AZ]

M.Aigner and G.Ziegler, Proofs from The Book, Springer-Verlag, 2001.

[BS]

A.Björner and R.P.Stanley, A combinatorial miscellany, Cambridge University Press, to appear.

[B]

B.Bollobas, Modern graph theory, Springer-Verlag, 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.1-2, Cambridge University Press, 1997-1999.