Math 566 (Algebraic Combinatorics), Winter 2018

MWF 11-12, 3866 East Hall
Instructor: Steven Karp
Office: 4839 East Hall
Office hours: Wednesday 9-10:30, Friday 1:30-3
Email: snkarp@umich.edu

Course description

Introduction to algebraic and enumerative combinatorics at the graduate level. Topics include: algebraic graph theory; enumeration of matchings and spanning trees; generating functions; integer partitions and Young tableaux. Prerequisites: familiarity with formal proofs and basic notions in combinatorics.

Textbook

• Richard P. Stanley, Algebraic Combinatorics: Walks, Trees, Tableaux, and More. Springer, 2013. (Also available from author's website.)
• Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition. Cambridge University Press, 2012. (Also available from author's website.)
• Richard P. Stanley, Enumerative Combinatorics, Volume 2. Appendix by Sergey Fomin. Cambridge University Press, 1999.
• Chris Godsil and Gordon Royle, Algebraic Graph Theory. Springer, 2001.
• Federico Ardila, "Algebraic and Geometric Methods in Enumerative Combinatorics". In Handbook of Enumerative Combinatorics, edited by Miklós Bóna. CRC Press, 2015.
• Ian P. Goulden and David M. Jackson, Combinatorial Enumeration. Reprint of the 1983 original. Dover Publications, 2004.
• Herbert S. Wilf, generatingfunctionology, 2nd edition. Academic Press, 1994.
• Mark Haiman, "Notes on the Matrix-Tree theorem and Cayley's tree enumerator".
• William Fulton, Young Tableaux. Cambridge University Press, 1997.
• Bruce E. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, 2nd edition. Springer, 2001.

Grading

The final grade will be based on several homework assignments (75%) and one in-class midterm exam (25%). There will not be a final exam.

Homework

Homework is due by the end of class time on the due date, submitted either in person or to my office (slid under the door). Late homework will not be accepted without prior approval. You are allowed to work with other students, but must include their names and write your solutions independently. You may also consult resources such as textbooks and online notes, which you must cite in your solutions. You are not allowed to copy solutions from other students or elsewhere, or to post or discuss homework problems online (including on websites such as Stack Exchange and MathOverflow). Any student determined to have engaged in academic dishonesty will receive a course penalty and be reported to the Office of the Assistant Dean for Undergraduate Education.

I may occasionally assign supplementary 'bonus' problems, which are not for credit. Students motivated to complete such problems should submit them to me individually (separately from homework submissions) at any time up to the last day of class.

Midterm exam

The midterm exam will be held in class on Friday, March 9th. The exam will be 'open notes': you may use your personal written or printed notes, but not any books or printouts thereof. The exam covers material up to and including the lecture of 02/12, and the first three homework assignments.

Accommodations for students with disabilities

The University of Michigan is committed to providing equal opportunity for participation in all programs, services and activities. Request for accommodations by persons with disabilities may be made by contacting the Services for Students with Disabilities (SSD) Office located at G664 Haven Hall. The SSD phone number is 734-763-3000. Once your eligibility for an accommodation has been determined you will be issued a verified individual services accommodation (VISA) form. Please present this form to me as soon as possible, and at least two weeks prior to the need for the accommodation.

Lectures

• 01/03: Adjacency matrix, graph eigenvalues, regular graphs
• 01/05: Eigenvalues of complete graphs, cycles, and paths
• 01/08: Eigenvalues of bipartite graphs and Cartesian products
• 01/10: Enumerating walks
• 01/12: Walk generating functions, walk asymptotics
• 01/15: Martin Luther King, Jr. Day (no class)
• 01/17: Graph homomorphisms
• 01/19: Enumerating perfect matchings, the Pfaffian
• 01/22: The Pfaffian method
• 01/24: Kasteleyn's formula, asymptotics
• 01/26: Rhombic tilings, plane partitions, lattice paths
• 01/29: Lindström–Gessel–Viennot lemma, MacMahon's formula
• 01/31: From perfect matchings to spanning trees (Temperley's bijection)
• 02/02: Graph Laplacian, matrix-tree theorem
• 02/05: Proof of the matrix-tree theorem
• 02/07: Directed matrix-tree theorem, de Bruijn sequences
• 02/09: Eulerian cycles, BEST theorem
• 02/12: Algebraic construction of de Bruijn sequences
• 02/14: Catalan numbers, generating functions
• 02/16: Catalan objects, formal power series
• 02/19: Lagrange's theorem
• 02/21: Lagrange's theorem
• 02/23: Series multisection
• 02/26: Vacation (no class)
• 02/28: Vacation (no class)
• 03/02: Vacation (no class)
• 03/05: MacMahon's master theorem, derangement numbers
• 03/07: Cayley's tree enumerator
• 03/09: Midterm exam
• 03/12: General matrix-tree theorem
• 03/14: q-numbers, inversion number generating functions
• 03/16: q-multinomial coefficients
• 03/19: Cyclic sieving phenomenon
• 03/21: Partitions, Schubert cells
• 03/23: q-identities
• 03/26: Partition identities, tableaux
• 03/28: Hook formula, posets
• 03/30: Young's lattice
• 04/02: Involutions in S_n
• 04/04: Robinson–Schensted–Knuth correspondence
• 04/06: Shadow lines, growth diagrams
• 04/09: Jeu de taquin
• 04/11: Rectification, evacuation, Knuth equivalence
• 04/13: Dual equivalence
• 04/16: Alternating permutations