Math 249: Algebraic Combinatorics—Fall 2017

Time and place
Subject matter
Homework and grades
Problem sets
List of lecture topics


(8/21) Welcome to Math 249! Watch this page for further information.


Mark Haiman,
Office hours Mondays 12:00-1:30 or by appointment

Time and place

MWF 3-4 pm, 289 Cory

Subject matter

I have decided to change the focus of the course this year and take as my organizing principle the combinatorics associated with Coxeter groups and root systems.

Following this approach, we will still naturally encounter many ideas and objects of interest in classical combinatorial enumeration, such as ordinary and exponential generating functions, symmetric functions, partitions, trees, lattice paths and so on. Our aim will be to connect these things with symmetric groups, considered as Coxeter groups, and with other data associated with root systems of 'type A,' so as to inquire about deeper phenomena and generalize to other root systems.

Although we will pass more quickly over certain topics which I traditionally cover in detail (such as species), in their place we should be able to introduce Hecke algebras and Kazhdan-Lusztig polynomials, and touch on some topics of current research interest, such as k-Schur functions, LLT pollynomials, and q,t-analogs of combinatorics associated with Dyck paths.


There is no required textbook for this course. I will give a self-contained presentation of the material in the lectures. You may, however, find some of the following useful as reference texts.

The online links above are available through the UC Libraries and should work from computers on campus. To access library resources from off campus, you can use the library Proxy Server.

Homework and grades

I'll post problem sets below at irregular intervals, generally due 2-3 weeks after posting. Grades will be based on homework. There will be no exams. To get an A in the course, you should do most of the problems, not skipping the harder ones. For a B (or less), some smaller fraction of the assigned work will suffice.

You may turn in problems in class, at my office (slip them under the door if I'm not in), or by e-mail in PDF format.

Problem sets

List of lecture topics

I will update this list as the course goes on. Any references to Vol. I (Chapters 1-4) of Stanley's book are to the 2nd edition.

  1. (8/23) The symmetric group. Two-line, one-line and disjoint cycle notation. Conjugacy classes Cλ and their sizes.
  2. (8/25) Binomial and multinomial coefficients. Counting multisets using generating functions.
  3. (8/28) More multiset counting: bijectively, or using distributions. Multivariate generating for the |Cλ|.
  4. (8/30) Intro to finite group representations. Defining and sign representations of Sn and Bn.
  5. (9/1) G-modules versus matrix representations. Submodules, quotients, direct sums, irreducibility. Examples in char 0 and char p. Group algebra; G-modules as kG-modules.
  6. (9/6) Complete reducibility and orthogonality. Characters of V⊗W and Hom(V,W). Interpretation of inner product as dimension of HomG(V,W). Examples.
  7. (9/8) Proofs of complete reducibility and orthogonality using Reynolds operator and Schur's lemma. Character table of S3.
  8. (9/11) Center of kG, projectors, uniqueness of isotypic components in a G-module. Orthogonality of columns in the character table. Formula |G|=∑ dim(Vi)2. Character table of S4.
  9. (9/13) Symmetric functions in finite and infinitely many variables. Partitions, Young diagrams, transpose, partial ordering. Monomial and elementary bases mλ and eλ.
  10. (9/15) Bases of complete homogeneous functions hλ and (over Q) power-sums pλ.
  11. (9/18) Frobenius characteristic map F : (Sn characters) → Λ(n). Inner product on Λ. Casimir element, Cauchy identity and orthogonality of power-sums.
  12. (9/20) Dual basis property <hλ, mμ> = δλμ. Induced characters. Calculation of F(1SλSn) = hλ.
  13. (9/22) Schur functions (classical definition). Pieri rule for eksλ. Schur functions as GLn characters (sketch).
  14. (9/25) Pieri rule for hksλ and corollaries.
  15. (9/27) The irreducible characters of the symmetric groups.
  16. (9/29) Murghahan-Nakayama rule. Cauchy identity for Schur functions and RSK.
  17. (10/2) RSK continued. Descent sets and compatible labellings.
  18. (10/4) RSK completed. Preview of skew Schur functions and Littlewood-Richardson coefficients.
  19. (10/6) Jeu-de-taquin. The two fundamental theorems. LR coefficients in terms of jeu-de-taquin.
  20. (10/9) Yamanouchi ("lattice") tableaux and the LR rule.
  21. (10/11) Dual equivalence and the fundamental theorems on jeu-de-taquin.
  22. (10/13) Dual equivalence continued. Introduction to species.
  23. (10/16) Exponential and mixed generating functions for species. Sum and product of species; examples. Formula for Stirling numbers.
  24. (10/18) Composition of species. Examples: generating function for Bell numbers; enumeration of permutations by cycle type (revisited).
  25. (10/20) Rooted trees and self-maps. Cayley's formula.
  26. (10/23) Weighted version of Cayleys's formula. Lagrange inversion formula via species.
  27. (10/25) Cycle index ZF of a species. Ordinary generating function for unlabeled structures.
  28. (10/27) Plethystic substitution. Interpretation of ZF[A] as an ordinary generating function for decorated, unlabelled structures.
  29. (10/30) Examples: counting unlablelled rooted trees (Polya's formula) and connected graphs, with computer demo.
  30. (11/1) (i) Formula for Plethystic 'logarithm' used in last lecture.
    (ii) Introduction to Coxeter groups: definition and main examples (Sn, Bn, dihedral groups, symmetry groups of regular polyhedra).
  31. (11/3) Degenerate and non-degenerate reflection representations, products. Coxeter arrangement; roots; Weyl chambers.
  32. (11/6) Coxeter systems (simple roots and reflections). Chambers are simplicial cones. Transitivity of group action on chambers. Chamber walks and Coxeter factorizations.
  33. (11/8) Length of reduced factorizations; Iwahori's theorem.
  34. (11/13) Classification of finite Coxeter groups. Preliminaries for Chevalley's theorem.
  35. (11/15) Statement of Chevalley's theorem; examples.
  36. (11/17) Dihedral group case of Chevalley's theorem. Divided difference operators.
  37. (11/20) Proof of Chevalley's theorem. Length generating function in terms of exponents.
  38. (11/27) Graded character of Sn on the polynomial ring. Garnir polynomials.
  39. (11/29) Construction of irreducible Sn modules.
  40. (12/1) Introduction to q-Kostka polynomials Kλ,μ(q), and their combinatorial and representation theoretic interpretations.

Back to top | Prof. Haiman's home page | Calendar