Math 249—Algebraic Combinatorics
Time and place: TuTh 11-12:30pm, Room 6 Evans Hall
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
- 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
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 1st edition
(Wadsworth & Brooks/Cole 1986; Cambridge Univ. Press 1997 hardcover,
1999 paperback), not the new 2nd edition (Cambridge
Univ. Press 2012).
- 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
- 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 An(x). Sorting permutation of a
word. Gessel's quasi-symmetric function Qn,D.
Formulas for An(x) in terms of
∑mmnxm and S(n,k).
- Lecture 6. Symmetry between major index and inversion number.
- Lecture 7. Combinatorial species: exponential generating function
associated with a species. Sum and product principles,
- 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.
- 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;
- Lecture 14. Plethysm. Plethystic inverse
of ZE–1. 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.
- 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
- 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 GLn, briefly.
- Lecture 21. Introduction to representation theory of finte
groups: complete reducibility, characters, orthogonality.
- Lecture 22. Frobenius characteristic map. Characters
of Sn from symmetric functions.
- Lecture 23. Restriction and induction
between Sn and Young subgroups;
Littlewood-Richardson coefficients. Construction of the irreducible
- Lecture 24. Bases of Vλ using Garnir
polynomials. Tensor products and the Kronecker problem.
- Lecture 25. Plethysm interpreted in terms
of GLn and Sn characters.
Wreath product related to composition of species.
- Lecture 26. Jeu-de-taquin, dual equivalence, first fundamental theorem.
[Top of page |
Prof. Haiman's home page]