Math 249: Algebraic Combinatorics—Fall 2017

Announcements

Professor

Time and place

Subject matter

Textbooks

Homework and grades

Problem sets

List of lecture topics

Announcements

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

Professor

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.

Textbooks

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.

Ian Macdonald, Symmetric functions and Hall polynomials (2nd ed), Oxford Univ. Press, 1995.
James E. Humphreys, Reflection groups and coxeter groups, Cambridge University Press, 1990. Available online.
Bruce Sagan, The Symmetric Group: Representations, Combinatorial Algorithms and Symmetric Functions (2nd ed), Springer, 2001. Available online.
William Fulton, Young Tableaux, London Math. Soc. Student Texts, Vol. 35, Cambridge Univ. Press 1997. Available online.
Richard Stanley, Enumerative Combinatorics, Vols. I (2nd ed) and II, Cambridge Univ. Press 1997, 2001, 2012. Available online: Volume I, Volume II Here is Stanley's EC web page
Francois Bergeron, Gilbert Labelle and Pierre Leroux, Combinatorial species and tree-like structures, Cambridge Univ. Press, 1998

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

Problem Set 1, due Wednesday, Nov. 8. Here is the LaTeX source in case you wish to use it as a template for composing solutions.
Problem Set 2, due Friday, Dec. 15. Here is the LaTeX source.

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.

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