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.

1. Enumeration: ordinary and exponential generating functions; Joyal's theory of species.
2. 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.
3. Order: posets, lattices and incidence algebras; order polynomials, zeta polynomials. Possibly some discussion of cd-indices and g-polynomials.
4. 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:

• 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 topics

• 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 examples.
• 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 t_n = n^n-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 Z_F(p₁, p₂, ...) 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. Z_F[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 correspondence.
• Lecture 23. Semi-standard jeu-de-taquin. Positivity of (generalized) Littlewood Richardson coefficients. Example: Pieri rules combinatorially.
• 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 S_n characters to symmetric functions.
• Lecture 26. Restriction, induction, Frobenius reciprocity.
• Lecture 27. Irreducible characters of S_n. Graded character of S_n on C[t₁,...,t_n].
• Lecture 28. Garnir polynomials, construction of irreducible representations.
• Lecture 29. Murgnahan-Nakayama rule.
• Lecture 30. Jacobi-Trudi identity (method of Gessel-Viennot and Lindström).
• Lecture 31. Bi-alternant formula for s_λ, interpretation as Weyl character formula for GL_n.
• Lecture 32. Principal specialization s_λ(1,q,...,q^n-1); 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.