Math 249: Algebraic Combinatorics—Spring 2024

Announcements

Professor

Time and place

Topics covered

Announcements

(1/15) Welcome to Math 249! Watch this page for further information.
(3/6) Problem sets for lectures 1-15 have been posted!
(3/15) As requested, I've also posted LaTeX source for the problem sets.
(4/13) No class Monday 4/15 (I have Covid). I'll send an update later as to whether we resume in person or online on Wednesday.
(4/16) Class on Wednesday 4/17 will be online. See announcement on bCourses for the link.
(4/22) Posted a third (less comprehensive) problem set on Lectures 16-31.

Professor

Mark Haiman,
Office hours by appointment

Time and place

MWF 3:10-4:00, Room 3 Evans

Topics covered

General concepts and techniques in combinatorial enumeration, emphasizing ordinary and exponential generating functions, with an introduction to combinatorial species. Additional topics may include Möbius inversion on partially ordered sets, hyperplane arrangements, and a little bit of matroid theory.

Combinatorics associated with geometry and representation theory of general linear groups GL_n and symmetric groups S_n, and possibly other reductive Lie groups and Weyl groups. I plan to cover symmetric functions, Schur functions, Young tableaux and jeu-de-taquin, Coxeter groups and the Bruhat order, and an introduction to quantum groups and crystal graphs.

Combinatorial description of q-analogs and q,t-analogs that arise in the above contexts. Depending on how much time we have, I hope to discuss some of the following: Hall-Littlewood polynomials, Kostka polynomials and charge; Macdonald polynomials, LLT polynomials, and k-Schur functions; q,t-Catalan numbers, parking functions and the shuffle theorem, with an introduction to the Burban-Schiffmann elliptic Hall algebra; Hecke algebras and Kazhdan-Lusztig polynomials.

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.

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
Ian Macdonald, Symmetric functions and Hall polynomials (2nd ed), Oxford Univ. Press, 1995.
Bruce Sagan, The Symmetric Group: Representations, Combinatorial Algorithms and Symmetric Functions (2nd ed), Springer, 2001. Available online.
James E. Humphreys, Reflection groups and coxeter groups, Cambridge University Press, 1990. Available online.
William Fulton, Young Tableaux, London Math. Soc. Student Texts, Vol. 35, Cambridge Univ. Press 1997. Available online.

Online links above are available via the UC Library from on campus, or off campus using the library proxy.

Homework and grades

I'll post occasional problem sets below, 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 at least half of the problems, including some of the harder ones. For a B (or less), some smaller fraction of the assigned work will suffice.

Please submit homework electronically by emailing me a PDF file (either typeset, or handwritten scanned or on a tablet). I've posted LaTeX source files in case you want to use them as templates for typesetting solutions.

Problem sets

Problem Set 1 (and LaTeX source file) on Lectures 1-6, due April 1
Problem Set 2 (and LaTeX source file) on Lectures 7-15, due April 15
Problem Set 3 (and LaTeX source file) on Lectures 16-31, due May 8 (Wednesday of final exam week)

List of lectures

I'll update this list after each lecture, summarizing what I covered.

(1/17) Idea of ordinary generating function (OGF) as weighted enumerator for a set. Examples: binomial and multinomial theorems, enumeration of multisets.
(1/19) Several methods for finding a formula for multiset coefficients. Rota's "12-fold way" table: entries that we know so far.
(1/22) Remaining entries in the 12-fold way: Stirling numbers S(n,k) of the 2nd kind; partition numbers p_k(n). Exponential and ordinary GF's for S(n,k).
(1/24) Signed and signless Stirling numbers s(n,k) and c(n,k) of the 1st kind; OGF and interpretation of c(n,k) as number of permutations of n with k disjoint cycles. Intro to partition generating functions, Young diagrams, transpose of a partition, partition identities. Odd parts vs. distinct parts.
(1/26) Bijection between partitions with odd parts and partitions with distinct parts. Teaser: Rogers-Ramanujan identities, with combinatorial interpretation, but not proof. q-Binomial and multinomial coefficients: definition, formula, q-binomial coefficients as OGF for partitions contained in a rectangle.
(1/29) Interpretation of q-binomial and multinomial coefficients by counting points on Grassmannians and partial flag varieties over F_q. q-Binomial theorems (usual and multiset versions) as partition identities.
(1/31) Introduction to combinatorial species: definition, examples, motivation. Exponential generating function (EGF) for counting structures of a given species on sets of any size; more examples.
(2/2) Constructions: sum, product, composition of species; indicator species. Examples. EGF's for Bell numbers and Stirling numbers. Mixed ordinary/exponential generating functions for counting structures of a species with weights.
(2/5) Applications to counting permutations by number of cycles, derangements, and permutations by cycle type.
(2/7) Species of trees. Number of rooted labelled trees on n vertices t_n = n ^n-1 by Joyal's method of comparing with species of self-maps. Cayley's formula and corollaries for counting rooted trees by number of children of each node.
(2/9) Lagrange inversion formula, derived combinatorially. Ordered trees, binary trees, and Catalan numbers.
(2/12) Cycle index Z_F(p₁, p₂, ...) of a species F. Specializations: EGF F(x) = Z_F(x,0,0,...), and OGF for unlabelled structures Z_F(x,x²,x³,...). Examples: Z_F = F(p₁) for linear orderings or any species whose structures have only trivial automorphisms; calculation for trivial species, permutations. Plethystic evaluation and decorated structures.
(2/14) OGF Z_F[A] for unlabelled decorated structures, where A = OGF for weighted enumeration of the decorating set. Examples: linear orderings, trivial species, cyclic orderings (unlabelled decorated structures are oriented necklaces with beads in the decorating set).
(2/16) Cycle index for product of species. Plethysm; cycle index for composition of species. Example: Polya's OGF for unlabelled rooted trees. Example: check composition rule on cycle indices found earlier for permutations and cyclic orderings.
(2/21) Plethystic logarithm. Cycle index for connected graphs weighted by q^e, (e = number of edges). Computer demo: OGF for connected graphs up to isomorphism, weighted by q^ex^v (v = number of vertices).
(2/23) Symmetric functions in finitely and infinitely many variables. Basis of monomial symmetric functions m_λ. Definition of elementary, complete homogeneous, and power-sum symmetric functions e_λ, h_λ, p_λ.
(2/26) Dominance partial ordering on partitions of n. Coefficients of e_λ in terms of m_μ. 'Rolling ball' proof that e_λ are a basis. Involution ω and proof that h_λ are a basis.
(2/28) Power-sums p_λ are a basis when coefficient ring R contains ℚ. Coefficients of h_λ in terms of m_μ. Hall inner product. Generalized Cauchy formula Ω[XY] = ∑_λ u_λ[X] v_λ[Y] for dual bases 〈 u_λ , v_μ 〉 = δ_λ,μ. Plethystic negative: f[-X] = ωf(-x₁, -x₂, ...) and why f[tX] = f(tx₁, tx₂, ...) does not imply f[-X] = f(-x₁, -x₂, ...).
(3/1) Orthogonality of power-sums. Example: computing 〈 h_μ, p_λ〉 (a) as coefficient of x^μ in p_λ; (b) using species. Vandermonde's identity. Schur functions. s_λ(x₁,...,x_n).
(3/4) Schur functions in infinitely many variables. Example: s_(1^k) = e_k. Weyl character formula and interpretation of s_λ(x₁,...,x_n) as a polynomial character of GL_n. Examples: exterior and symmetric powers of the defining representation ℂⁿ of GL_n.
(3/6) Young tableaux. Kostka numbers K_λ,μ. Pieri rule. Coefficient of s_λ in e_μ given by K_λ^*,μ. Bernstein operators.
(3/8) Commutation relations for Bernstein operators with each other and with e_k^⊥. Dual Pieri rule for e_k^⊥ s_λ. Orthonormality of Schur functions.
(3/11) Triangularities, action of involution: ω s_λ = s_λ^*. Combinatorial formula s_λ = ∑_λ K_{λ,μ m_μ =
∑_{T ∈ SSYT(λ)} x^T}. Construction of irreducible representations of GL_n using Schur functors.
(3/13) Schur functors more explicitly: V_λ as the space spanned by products of left-justified minors of an n × l matrix of indeterminates M; products of minors corresponding to the columns of a semistandard Young tableaux form a weight basis. Example: reduction to the basis in V_(2,1). Cauchy identity for Schur functions interpreted as the character of GL_n × GL_l on polynomials in the entries of M.
(3/15) Introduction to representation theory of finite groups. Representations as modules for the group algebra ℂG. Characters and their basic properties. Inner product; 〈χ_V, χ_W〉 = dim Hom_G(W,V). Schur's Lemma and orthonormality of characters. Complete reducibility (Maschke's theorem). Using characters to find multiplicities of irreducibles. Examples: trivial representation and regular representation. Decomposition ℂG ≅ ⊕_i End_ℂ(V_i). Number of irreducible characters equals number of conjugacy classes.
(3/18) Frobenius characteristic map F: (S_n characters) → (symmetric functions homogeneous of degree n). Properties: F is an isometry; F(1_{S_μ}^S_n) = h_μ. Theorem: irreducible characters correspond to Schur functions.
(3/20) Murnaghan-Nakayama rule for characters in terms of connected ribbon tableau. Example: character table of S₄.
(3/22) Coefficients of Ω[XY...Z] in terms of products of Schur functions are equal to Kronecker coefficients for tensor products of S_n characters, hence are non-negative integers. Open problem: find a combinatorial rule. Interpretation of cycle index Z_F of a species as formal sum of Frobenius characteristics of permutation representations F([n]) of S_n. Multiplication of Frobenius characteristics corresponds to induced product of characters. Interpretation in terms of product of species.
(4/1) Plethysm of Frobenius characteristics ↔ induced character of V⊗W^⊗k from wreath product S_k⋉S_l^k to S_kl. Proof using species interpretation of plethysm. GL_n character interpretation as composition of Schur functors. Corollary to either interpretation: plethysm of Schur functions s_λ*s_μ = ∑ f_λ,μ^ν s_ν has non-negative integer coefficients f_λ,μ^ν. Open problem: find a combinatorial rule.
(4/3) Crystal graph structure on semistandard tableaux of straight or skew shape. Example: crystal graph for the irreducible representation V_(2,1) of GL₃. Remarks on quantum groups and crystal bases in general. Matrix coefficients of generators of 𝒰_q(gl₃) in the example for V_(2,1).
(4/5) Jeu-de-taquin. Preservation of crystal graph. Yamanouchi words and description of the crystal graph on SSYT(λ) for straight shapes (partition diagrams). Corollaries: uniqueness of jeu-de-taquin rectification; Littlewood-Richardson rule for Schur function expansion of skew Schur functions and products of Schur functions. RSK correspondence. RSK insertion = jeu-de-taquin rectification.
(4/8) Introduction to Hall-Littlewood polynomials H_μ(x;q) and q-Kostka coefficients K_λ,μ(q). Formula for K_λ,μ(q) in terms of q-Kostant partition function. Stability. Example: Schur function expansion of H_(2,2,1)(x;q). Geometric and representation theoretic reasons for positivity K_λ,μ(q)∈ℕ[q]. Open problem: combinatorial description for Lie types other than GL_n.
(4/10) Jing operators. 'Dual Pieri rule' for e_k^⊥ acting on Hall-Littlewood polynomials.
(4/12) Monomial expansion of ω H_μ(X;q) in terms of row-strict tabloids q-counted by number of 'increasing triples.' Contents, attacking pairs, and definition of LLT polynomial 𝒢_ν(x;q) associated to a tuple ν of skew Young diagrams. Theorem (proof later): 𝒢_ν(X;q) is symmetric.
(4/17) Quasisymmetric functions. Monomial and Gessel bases. Standardization of semistandard tableaux. Formula for (skew) Schur functions in terms of Gessel quasisymmetric functions indexed by standard tableaux. Superization ω_Y f[X+Y] of a symmetric function. Superized (skew) Schur functions as generating functions for super tableaux.
(4/19) Standard tableau formula for super Schur functions in terms of super Gessel quasisymmetric functions. Symmetric versus quasisymmetric superization for general symmetric functions. Standardization for tableaux on a tuple of diagrams in the LLT setting; preservation of number of attacking inversions.
(4/22) Proof of the symmetry theorem for LLT polynomials.

Lecture notes are on bCourses (currently through Lecture 31).