Math 565: Combinatorics and Graph Theory

Fall 2007

Course meets: Tuesday and Thursday 11:40-1:00 in 2866 East Hall.

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

Office hours: Tuesday 2:40-3:40 and Thursday 4:10-5: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 theory-building).

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