Math 566: Combinatorial Theory

Winter 2015

Course meets: Tuesday and Thursday 1:10-2:30 in 4088 East Hall.

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

Office hours: Tuesday 2:40-4:00 and Thursday 4:10-5:30 in 4868 East Hall.

Grader: Benjamin Branman, bbranman@umich.edu.

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

Level: introductory graduate/advanced undergraduate.

Prerequisites: Familiarity with formal proofs, and with basic notions of combinatorics. Linear algebra will be used throughout.

Student work expected: several problem sets.

Synopsis: This course is an overview of applications of algebra (mostly linear algebra) to combinatorics (mostly enumerative combinatorics). Topics include: introduction to algebraic graph theory; applications of linear algebra to enumeration of matchings, tilings, and spanning trees; combinatorics of electric networks; partially ordered sets, integer partitions, and Young tableaux. The course will emphasize problem solving (as opposed to theory-building).

Optional text: R. P. Stanley, Algebraic Combinatorics: Walks, Trees, Tableaux, and More, Springer, 2013. The text of this book (without exercises) is available at the link above.

Additional texts (none required):

• A. Björner and R. P. Stanley, A combinatorial miscellany, L'Enseignement Math., Monograph No. 42, 2010.
• J. H. van Lint and R. M. Wilson, A course in combinatorics , Cambridge University Press, 1996.
• R. P. Stanley, Enumerative combinatorics, vol. 1-2, Cambridge University Press, 1997-1999.

Topics covered (very tentative list, subject to change):

ALGEBRAIC GRAPH THEORY Spectra of graphs Walks on a cube Sperner's theorem Matrix-tree theorem Eulerian tours Domino tilings TOPICS IN ENUMERATION Cayley's Theorem De Bruijn Sequences Rook polynomials Polya theory PARTITIONS AND TABLEAUX Partitions. Pentagonal Number Theorem q-binomial coefficients Hooklength formula Young's lattice The Schensted correspondence Tableaux and involutions