Math 249—Algebraic Combinatorics
Time and place: MWF 3:00-4:00pm, Room 5 Evans
Course control number: 54527
Professor: Mark Haiman
Office: 855 Evans
Office hours: By appointment
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.
- 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:
- 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 will be based entirely on
homework. Here is the running list of
problems. Problems will be added for each lecture. They are due
the second Monday following the lecture, except: the next class day if
the Monday is a holiday, or May 9 (first day of finals) if the due
date would be May 2 (reading/review week).
- Lecture 1. Counting basics: permutations and
k-permutations, binomial, multinomial and multiset
coefficients. Introduction to ordinary generating functions.
- Lecture 2. Formal power series. q-Enumeration of
permutations and multiset permutations; q-binomial and
multinomial coefficients. q-Binomial theorem. Enumeration
of subspaces and flags in vector spaces over finite fields.
- Lecture 3. Partitions and their generating functions.
q-Binomial theorem as a partition identity.
- Lecture 4. Second form of the q-binomial theorem. Euler's
pentagonal number theorem and Franklin's combinatorial proof.
- Lecture 5. Rota's 12-fold way. Stirling numbers of the 2nd kind
and (signless) Stirling numbers of the 1st kind. Simple
identities involving Stirling numbers.
- Lecture 6. Joyal's definition of species. Exponential
generating functions. Sum and product principle. Simplest
- Lecture 7. Composite species and the composition principle.
Examples: preference orders, Bell numbers, Stirling numbers of
both kinds, derangements.
- Lecture 8. The species of rooted trees. Formula
tn = nn-1 by (i) comparison with the
species of self-maps, (ii) Lagrange inversion formula.
- Lecture 9. Combinatorial proof of Lagrange inversion using
species and Cayley's tree enumerator.
- Lecture 10. Cycle index ZF(p1,
p2, ...) of a species. Specialization to EGF for
labelled F structures and OGF for unlabelled structures.
Examples: species without automorphisms, trivial species, species
of permutations. Sum and product principles.
- Lecture 11. Plethysm and plethystic
evaluation. ZF[A] as ordinary generating
function for decorated F structures up to isomorphism.
Composition principle. Example: cycle index of the Bell species.
- Lecture 12. More examples, with computer demo: OGF for
isomorphism types for the species of rooted trees, graphs and
connected graphs (weighted by number of edges), and unrooted trees
(from connected graphs, or using centers and bicenters).
- Lecture 13. Matrix-Tree Theorem and applications.
- Lecture 14. Symmetric polynomials in finite and infinitely many
variables. Dominance ordering on partitions. Monomial and
elementary symmetric functions.
- Lecture 15. Fundamental theorem of symmetric functions. Complete
homogeneous symmetric functions. Generating
functions E(t), H(t).
- Lecture 16. Power sums. Involution ω. Inner
product. Cauchy identity for dual bases.
- Lectures 17-18. Schur functions: tableau definition, symmetry
theorem and crystal operators. Statement of RSK. Orthonomality
of Schur basis. Pieri rules. Triangularities.
- Lecture 19. Schensted correspondence in detail; Knuth's
extension. Proof of RSK.
- Lecture 20. Jeu-de-taquin. Dual equivalence. Dual equivalence
on straight shapes. Simulation of Schensted insertion by slides.
- Lecture 21. `Switching' lemma and consequences. Fundamental
theorems of jeu-de-taquin.
- Lecture 22. Knuth equivalences. Symmetry properties of Schensted
- Lecture 23. Semi-standard jeu-de-taquin. Positivity of (generalized)
Littlewood Richardson coefficients. Example: Pieri rules
- No class Friday, Mar 18 (for this lecture and the one I
missed when sick in January, I'll hold makeup lectures during RRR week).
- Lecture 24. Representation theory of finite groups in a nutshell.
- Lecture 25. Characters. Frobenius characteristic map
from Sn characters to symmetric functions.
- Lecture 26. Restriction, induction, Frobenius reciprocity.
- Lecture 27. Irreducible characters of Sn.
Graded character of Sn
- Lecture 28. Garnir polynomials, construction of irreducible
- Lecture 29. Murgnahan-Nakayama rule.
- Lecture 30. Jacobi-Trudi identity (method of Gessel-Viennot and
- Lecture 31. Bi-alternant formula for sλ,
interpretation as Weyl character formula for GLn.
- Lecture 32. Principal
hook formula for number of standard Young tableaux.
- Lecture 33. LLT polynomials: definitions, basic properties,
standardization, statement of symmetry theorem.
- Lecture 34. Proof of the symmetry theorem for LLT polynomials.
- Lecture 35. Hall-Littlewood polynomials via LLT.
- Lecture 36. Characterization of H-L polynomials by triangularity
and orthogonality properties.
- Lecture 37. More about H-L polynomials. q-Kostka numbers.
- Lecture 38. Pieri rule and classical formulas for H-L polynomials
- Extra Lecture, Mon May 2, 2-4pm, 72 Evans. Macdonald
polynomials. Charge formula for q-Kostka numbers.
[Top of page |
Prof. Haiman's home page]