Math 249: Algebraic Combinatorics—Spring 2020

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

Announcements

(3/17) Updated Problem Set 1 again to fix another mistake in problem 13.
(3/11) Problem Set 1 has been updated to fix the missing portion of problem 13.
(3/10) While in-person classes are suspended at Berkeley because of corona virus, I'll hold class on Zoom. I've sent out the link to join the Zoom meeting by email. If you didn't receive it, please let me know.
(2/28) Problem Set 1 posted; due March 18 (last class before Spring Break).
(1/21) Welcome to Math 249! Watch this page for further information.

Professor

Mark Haiman,
Office hours by appointment

Time and place

MW 2-3:30, 736 Evans

Subject matter

We'll begin with some fundamentals of combinatorial enumeration and discuss combinatorial species, which serve as a unifying framework for various kinds of generating functions.

Next we will turn to the combinatorial theory associated with symmetric functions and representations of the symmetric and general linear groups, including Young tableaux, jeu-de-taquin, and the Frobenius characteristic map. We will see how to re-interpret the cycle index of a combinatorial species using these ideas.

Finally, we will consider "q-analogs" and even "q,t-analogs" of combinatorial concepts encountered in the first part of the course. These may include some or all of: Hall-Littlewood and Macdonald polynomials, Hecke algebras and LLT polynomials, k-Schur functions, and q,t-analogs of combinatorics associated with Catalan numbers.

Depending on how much time we have, we may also discuss how some of the combinatorics associated with the symmetric and general linear groups—which are the Coxeter groups and Lie groups associated with root systems of type A—extends to other root systems.

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.

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 will need to submit problem sets by e-mail in PDF format, since in-person classes have been cancelled and access to the campus is curtailed because of the Covid-19 pandemic.

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. (1/22) The 12-fold way. Generating functions for binomial and multichoose coefficients. Alternative methods for multichoose coefficients. Partition generating functions. Odd parts = distinct parts. Teaser: Rogers-Ramanujan identities.
  2. (1/27) Counting principles for ordinary GF's. More partition identities. Combinatorial intermpretation of Rogers-Ramanujan identities. Stirling triangle and an OGF for Stirling numbers S(n,k). Teaser: exponential GF's for Stirling and Bell numbers. First kind Stirling numbers s(n,k); signless Stirling numbers c(n,k) and what they count.
  3. (1/29) Stirling summation formula. Species preview: counting combinatorial structures on a set of n labels. How linear orderings differ from permutations. Exponential generating functions. Zig-zag permutations: a non-species with a nice exponential GF. Definition of species. Sum and product of species. Indicator species. Example: identity of species L = 1 + X L for linear orderings, giving L(x)=1/(1-x).
  4. (2/3) More product examples: exponential and mixed GF's for S(n,k). Composite species. Examples: Stirling numbers of both kinds, double partitions, derangements. Enumerating permutations by cycle type. Rooted trees.
  5. (2/5) Number of rooted tees = nn-1 by comparing with the species of maps. Cayley's generating function for trees. Lagrange inversion formula; combinatorial proof using species and Cayley's formula. Catalan numbers: parenthesis strings, Dyck paths, ordered trees.
  6. (2/10) More on Catalan numbers Cn and their ordinary GF C(x). Computing Cn by (a) solving quadratic for C(x), (b) Lagrange inversion, (c) rotating extended Dyck paths. Dyck path formulation of Lagrange inversion. Teaser: q-Catalan numbers (two kinds) and q,t-Catalan numbers.
  7. (2/12) Cycle index of a species. How it gives the exponential GF for labelled structures and the ordinary GF for unlabelled structures. Examples: species with no non-trivial automorphisms (linear orderings, ordered trees), the trivial species, the species of permutations. Plethystic evaluation and unlabelled decorated structures.
  8. (2/19) Unlabelled decorated structures revisited. Plethysm and plethystic evaluation. Composition principle for cycle indices. Examples: trivial species; Polya's generating function for unlabelled rooted trees. Cycle index for graphs and connected graphs (preview).
  9. (2/24) Cycle index for simple graphs in detail. Plethystic analog of logarithm. How to solve for the cycle index of connected graphs. Computer demo: (1) unlabelled rooted trees, (2) counting connected graphs with n vertices and e edges up to isomorphism.
  10. (2/26) Symmetric functions in finite and infinitely many variables. Basis of monomial symmetric functions. Elementary symmetric functions and their coefficients in the monomial basis. Partial ordering on partitions of n. Transposing partitions is order-reversing.
  11. (3/2) Elementary symmetric functions eλ and complete homogeneous symmetric functions hλ. Generating functions for en and hn. Proof that the eλ and hλ are bases. Involution ω. Inner product on Λ. Cauchy formulas for eλ and hλ. Casimir element of a pairing; general form of Cauchy formulas.
  12. (3/4) Basis of power-sums pλ (over ℚ). Plethystic evaluation. Formula ωpλ = (-1)n-l(λ)pλ. Orthogonality via Cauchy formula for power-sums. Schur functions: Jacobi's definition, examples. Schur functions in infinitely many variables.
  13. (3/9) The Weyl character formula for GLn. Schur functions = irreducible GLn characters. Bernstein's raising operators Bm. Formula Ω[AX]⊥ f(X) = f[X+A] and plethystic expression for Bm.
  14. (3/11) Pieri and dual Pieri rules using Bernstein operators. Orthonormality of Schur functions. Combinatorial formula Kλ,μ = number of semistandard Young tableaux of shape λ and weight μ.
  15. (3/16) Skew Schur functions. Littlewood-Richardson coefficients and tensor products of GLn characters. Representations and characters of finite groups: basic notions.
  16. (3/18) [Whiteboard slides] One-lecture minicourse on representations and characters of finite groups. Characters, invariants, Reynolds operator, complete reducibility, inner product, orthonormality of irreducibles. Regular representation, number of irreducibles = number of conjugacy classes. Example: character tables of S2 and S3.
  17. (3/30) [Whiteboard slides] Frobenius characteristic map F. Induction, restriction and Frobenius reciprocity. Description of IndHG(1). Computation of F IndHG(1) for G = Sn and H = Sλ using species. Meaning of the cycle index of a species in general. Theorem: F is an isometry. Theorem: the irreducible characters χλ of Sn are given by F χλ = sλ.
  18. (4/1) [Whiteboard slides] Example: character table of S4. Murgnahan-Nakayama rule. Induction product and representation theoretic interpretation of Littlewood-Richardson coefficients. Variations: skew and multi-index coefficients.
  19. (4/6) [Whiteboard slides] Jeu-de-taquin slides on standard tableaux. Preservation of descent set. Standardization and slides on semi-standard tableaux. Switching theorem.
  20. (4/8) [Whiteboard slides] Dual equivalence, elementary dual equivalences. All tableaux of a straight shape are dual equivalent. 1st and 2nd fundmamental theorems for jeu-de-taquin. Combinatorial interpretation of Littlewood-Richardson coefficients. Yamanouchi tableaux and the classical Littlewood-Richardson rule.
  21. (4/13) [Whiteboard slides] Robinson-Schensted-Knuth (RSK) algorithm for permutations and standard tableaux. Interpretation of P and Q tableaux in terms of jeu-de-taquin and dual equivalence. Knuth relations and dual Knuth relations. Steps towards the property (P(π−1),Q(π−1)) = (Q(π),P(π)).
  22. (4/15) [Whiteboard slides] Property (P(π−1),Q(π−1)) = (Q(π),P(π)) completed. RSK for words and bipartite partitions. Combinatorial interpretation of the Cauchy formula. Warm-up for Hall-Littlewood polynomials and q-Kostka coefficients Kλ,μ(q).
  23. (4/20) [Whiteboard slides] Definition of Hall-Littlewood polynomials and Kλ,μ(q). Examples. q-Analog of Kostant's partition function. Kλ,μ(q) as a q-analog of Kλ,μ. Positivity and charge (definition).
  24. (4/22) [Whiteboard slides] Properties and examples of charge. Cyclage and catablolism. Representation theory & geometry interpretation of Weyl character formula and Kλ,μ(q) in terms of the flag variety and its cotangent bundle. Meaning and non-negativity of Kλ,μ(q) for any root system; combinatorial interpretation is an open problem. Jing's operators. Preview of triangularity and orthogonality.
  25. (4/27) [Whiteboard slides] Characterization of Hall-Littlewood polynomials by upper and lower triangularities. Orthogonality. Example: evaluation, combinatorics, and representation-theoretic interpretation of H1n(x;q) and fλ(q) = K˜λ,1n(q).
  26. (4/29) [Whiteboard slides] Macdonald polynomials. Characterization by orthogonality, triangularity and normalization. Reduction to Hall-Littlewood polynomials when q=0. Examples. Combinatorial formula: statement and sketch of proof. Charge formula for Kλ,μ(q) from the combinatorial formula for Macdonald polynomials.
Back to top | Prof. Haiman's home page | Calendar