Spring 2012

**Course control number:** 54535

**Professor:** Mark Haiman

**Office:** 855 Evans

**Office hours:** W 10:30am-12:30pm

**Phone:** (510) 642-4318

**Syllabus:** Introduction to combinatorics at the graduate
level, with topics from the four general areas below.

- Enumeration: ordinary and exponential generating functions;
Joyal's theory of
*species*. - Symmetric functions and their connection with representation
theory of symmetric groups and general linear groups; tableau
combinatorics;
*q*-analogs in the theory of symmetric functions. Possibly some discussion of combinatorics and representation theory related to*(q,t)*-Catalan numbers and parking function enumeration. - Order: posets, lattices and incidence algebras; order
polynomials, zeta polynomials. Possibly some discussion of
*cd*-indices and*g*-polynomials. - Geometric combinatorics: polytopes, hyperplane arrangements,
simplicial complexes; Stanley-Reisner rings and Cohen-Macaulay
complexes;
*f*-vectors.

**Prerequisites:** Algebra background equivalent to 250A.

**Required text:** Richard P. Stanley, * Enumerative
Combinatorics, Vols. I & II.* Cambridge Univ. Press 1999, 2000.

**Recommended additional reading:**

- F. Bergeron, Gilbert Labelle, and Pierre Leroux,
*Combinatorial species and tree-like structures.*Cambridge Univ. Press, 1998. - William Fulton,
*Young Tableaux.*London Math. Soc. Student Texts, Vol. 35, Cambridge Univ. Press 1997. - Bruce Sagan,
*The Symmetric Group: Representations, Combinatorial Algorithms and Symmetric Functions, 2nd ed.*Springer, New York 2001. - Günter M. Ziegler,
*Lectures on Polytopes.*Birkhäuser Verlag, 2000.

**Homework and grading:** Grading is based entirely on homework;
no exams. Officially, homework is due the second Tuesday following
the lecture for which it is assigned, or the next class day if that
Tuesday is a holiday. Problems for the last two weeks of lectures are
due by Friday, May 11, the last day of final exam week. To keep up
with the lectures you should try to do the problems on time. However,
I don't promise to grade and return homework in a timely fashion, so I
don't insist that you turn it in on time.

Here is the running list of homework
problems, organized by lecture. For your convenience if you are
writing solutions on a computer, you can also download
the LaTeX source file. Note: problems
from Stanley Vol. I refer to the *1 ^{st} edition*
(Wadsworth & Brooks/Cole 1986; Cambridge Univ. Press 1997 hardcover,
1999 paperback), not the new 2

**Lecture topics**

- Lecture 1. Basic enumeration: the 12-fold way. Counting multisets. Recurrences: Pascal and Stirling triangles.
- Lecture 2. Recurrence for partition numbers. Ordinary generating functions. Examples for binomial and multiset coefficients, partitions and compositions (with or without part restrictions). An OGF for Stirling numbers.
- Lecture 3. Formal power series. Young diagrams. Partition identities. Partition interpretation of Rogers-Ramanujan identities.
- Lecture 4.
*q*-counting by inversions.*q*-factorials and*q*-multinomial coefficients. Counting subspaces of finite vector spaces.*q*-binomial theorem. - Lecture 5. Descents, major index, Eulerian
polynomials
*A*. Sorting permutation of a word. Gessel's quasi-symmetric function_{n}(x)*Q*. Formulas for_{n,D}*A*in terms of_{n}(x)*∑*and_{m}m^{n}x^{m}*S(n,k)*. - Lecture 6. Symmetry between major index and inversion number. Foata map.
- Lecture 7. Combinatorial species: exponential generating function associated with a species. Sum and product principles, applications.
- Lecture 8. Species of binary trees and ordered trees. Digression into Catalan combinatorics: Dyck paths, triangulations, enumerating Dyck paths using periodic paths. Composition principle, simple applications.
- Lecture 9. Unordered trees. Cayley's Theorem. Lagrange inversion formula from Cayley's Theorem and species.
- Lecture 10. Lagrange inversion in terms of Dyck paths.
*q*-Lagrange inversion. - Lecture 11. Parking functions, bijections with
trees,
*q*-enumeration of parking functions and trees using breadth-first and depth-first search. - Lecture 12. Matrix-Tree Theorem. Cycle index of a species (introduction).
- Lecture 13. Cycle index continued: sum and product principles; plethystic substitution.
- Lecture 14. Plethysm. Plethystic inverse
of
*Z*. Counting rooted trees and connected graphs up to isomorphism. For the computer demo in class I used this Mathematica Notebook; here also is a PDF printout._{E}–1 - Lecture 15. Symmetric functions. Bases of monomials and elementary symmetric functions. Dominance ordering on partitions.
- Lecture 16. Complete homogeneous symmetric functions, power-sum
symmetric functions, generating function
*H(t)*. The involution*ω*. Combinatorial definition and symmetry of Schur functions. - Lecture 17. Crystal operators of Lascoux and Schützenberger. Kostka numbers. Hall inner product and Cauchy kernel.
- Lecture 18. Robinson-Schensted-Knuth correspondence, Cauchy identity, orthonormality of Schur functions.
- Lecture 19. Dual cauchy identity, action of
*ω*on Schur functions. Plethysm/λ-ring operations. Pieri rules and dual Pieri rules. - Lecture 20. Jacobi/Weyl character formula; Jacobi-Trudi
identity. Representation theory of
*GL*, briefly._{n} - Lecture 21. Introduction to representation theory of finte groups: complete reducibility, characters, orthogonality.
- Lecture 22. Frobenius characteristic map. Characters
of
*S*from symmetric functions._{n} - Lecture 23. Restriction and induction
between
*S*and Young subgroups; Littlewood-Richardson coefficients. Construction of the irreducible modules_{n}*V*._{λ} - Lecture 24. Bases of
*V*using Garnir polynomials. Tensor products and the Kronecker problem._{λ} - Lecture 25. Plethysm interpreted in terms
of
*GL*and_{n}*S*characters. Wreath product related to composition of species._{n} - Lecture 26. Jeu-de-taquin, dual equivalence, first fundamental theorem.