### 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, fomin@math.lsa.umich.edu

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

Course homepage: http://www.math.lsa.umich.edu/~fomin/565.html

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:

 INTRODUCTION Cayley's Theorem De Bruijn Sequences Hooklength formula ALGEBRAIC GRAPH THEORY Spectra of graphs Walks on a cube Sperner's theorem Matrix-tree 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 q-binomial 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.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.