Math 249: Algebraic Combinatorics—Fall 2016

Announcements

Professor

Time and place

Subject matter

Textbooks

Homework and grades

Problem sets

List of lecture topics

Announcements

(8/15) Welcome to Math 249! Watch this page for further information.
(9/7) Problem Set 1 posted, due in 3 weeks.
(10/19) Problem Set 2 posted, due in 3 weeks.
(11/29) Problem Set 3 posted, due during finals week.

Professor

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

Time and place

MWF 3-4 pm, Latimer 105

Subject matter

The first part of the course will be an introduction to classical combinatorial enumeration, ordinary and exponential generating functions and their unification using the theory of species, along with related topics such as partition identites and Lagrange inversion.

Next we will turn to combinatorial theory of symmetric functions and Young tableaux, including Hall-Littlewood, LLT and Macdonald polynomials, and their connections with representations of the symmetric and general linear groups, and with the geometry of flag varieties and Hilbert schemes.

If we have time, I might also discuss the relationship of Hall-Littlewood and LLT polynomials to Kazhdan-Lusztig theory.

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

The UC library links above should work from computers on campus. You can access library resources from off campus by using 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.

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

Problem sets

Problem Set 1, due Wednesday 9/28. Here is the LaTeX source file, in case you want to use it as a template for composing typeset solutions.
Problem Set 2, due Wednesday 11/9, with LaTeX source file. [Problem 9 corrected 11/29]
Problem Set 3, with LaTeX source file. Solutions submitted on paper at my office are due by Tuesday 12/13; email solutions by Friday 12/16.

List of lecture topics

I will update this list as the course goes on. Pointers to Stanley Vol. I (that is, Chapters 1-4) refer to the 2nd edition.

(8/24) Ordinary generating functions. Example: counting ordered rooted trees (Catalan numbers).
(8/26) Some more things enumerated by Catalan numbers. Formal power series and how to work with them. [Stanley 1.1]
(8/29) The "12-fold way" of basic enumeration problems. Binomial and multiset coefficients; distributions. Stirling numbers (2nd kind). [Stanley 1.9]
(8/31) 12-fold way continued. Binomial and multinomial theorems. q-Binomial and q-multinomial coefficients. [Stanley 1.7]
(9/2) Lattice path and finite field interpretations of q-binomial and q-multinomial coefficients. Multiset coefficients via generating functions.
(9/7) 1st and 2nd kind Stirling numbers; ordinary generating functions.
(9/9) Partition generating functions. Partititions with distinct parts, odd parts, or other restrictions. q-Binomial Theorems. [Stanley 1.8]
(9/12) Applications of q-Binomial Theorems: Cauchy's identity, Jacobi Triple Product, Euler's pentagonal number formula and recurrence for p(n).
(9/14) Rogers-Ramanujan identities (discussion without proof). Gessel quasi-symmetric functions Q_n,D(x) and enumeration of permutations by descent set.
(9/16) More on Q_n,D(x). Enumeration of permutations by number of descents and by major index. Eulerian polynomials in terms of Stirling numbers. [Stanley 1.4]
(9/19) Symmetry and significance of ∑_{w∈S_n} q^inv(w) t^maj(w).
(9/21) Definition of combinatorial species. Exponential generating function of a species.
(9/23) Sum and product of species. Examples. Exponential generating function and explicit formula for 2nd kind Stirling numbers S(n,k).
(9/26) Composition of species. Examples. Counting rooted trees using function graphs. [Stanley 5.1]
(9/28) Mixed ordinary/exponential generating functions for species enumerated with weights.
(9/30) Lagrange inversion formula. Combinatorial proof using generic species and Cayley's tree enumerator. [Stanley 5.4]
(10/3) Matrix-Tree Theorem. [Stanley 5.6]
(10/5) Cycle index of a species. Specializations to the exponential G.F. for labelled structures and the ordinary G.F. for unlabelled structures.
(10/7) Cycle index of sums, products, and composite species; examples.
(10/10) Polya's formula for the ordinary G.F. for unlabelled rooted trees. Plethystic logarithm. Ordinary G.F.'s for unlabelled graphs, connected graphs, and unrooted trees, counted by number of vertices and number of edges. Computer demo.
(10/12) Symmetric functions in finite and infinite numbers of variables. Basis of monomial symmetric functions. Partial ordering on partitions of n. Theorem that transpose reverses the ordering.
(10/14) Bases of elementary and complete homogeneous symmetric functions, and their coefficients in terms of monomial symmetric functions. Classical fundamental theorem of symmetric functions.
(10/17) Inner product and Cauchy identity. Basis of power-sums. Orthogonality of power-sums.
(10/19) Plethystic substitution; involution ω. Combinatorial definition and symmetry of Schur functions s_λ (including skew Schur functions).
(10/21) RSK for permutations. Preservation of descent sets.
(10/24) Orthogonality of Schur functions and formula ω s_λ = s_λ^* via RSK.
(10/26) Adjoints. Basis-free Cauchy identity Ω[AX]^⊥ f = f[X+A]. Pieri formulas. Littlewood-Richardson coefficients c^ν_λμ = ⟨s_ν, s_λs_μ⟩ = ⟨s_λ, s_ν/μ⟩.
(10/28) Representations of GL_n and their characters; examples. Symmetry of characters. Statement of the Weyl character formula for GL_n.
(10/31) Schur functions as GL_n characters and related unsolved, semi-solved and solved combinatorial problems.
(11/2) Constructing irreducible GL_n representations. Jacobi-Trudi identity. Representations of S_n and finite groups: basic properties.
(11/4) Representations of S_n and finite groups: examples. Frobenius characteristic map F; isometry property; relation to cycle index of a species. Computation of F(1^S_n_{S_μ}) = h_μ.
(11/7) The irreducible characters of S_n.
(11/9) Graded character of S_n on C[z₁,...,z_n]. Generalized hook formula for s_λ(1,t,...,t^n-1) and hook formula for number of standard Young tableaux of shape λ.
(11/14) Construction of irreducible representations of S_n.
(11/16) Jeu de taquin: slides, dual equivalence.
(11/18) Jeu de taquin: fundamental theorems.
(11/21) Jeu de taquin for semistandard tableaux. Yamanouchi tableaux (and a bit about crystals). Littlewood-Richardson rule.
(11/28) Hall-Littlewood polynomials H_μ and raising operators.
(11/30) K_λ,μ(q) as q analog of weight multiplicity, in terms of q-root partition function for GL_n. Characterization of H_μ by upper and lower triangularities. Sketch of geometric proof of positivity of K_λ,μ(q) using T^*(G/B).
(12/2) Charge of words and tableaux. Combinatorial interpretations of K_λ,μ(q) in terms of charge and counterclockwise fillings. Sketch of proof using upper and lower triangularities.