Math 249: Algebraic Combinatorics—Spring 2015

Announcements

Professor

Time and place

Textbooks

Homework and grading

Outline

List of topics by lecture

Problem sets

Announcements

(5/1) Problem Set 5 posted, due May 15, the last day of final exams. There is no final exam for this class.
(4/15) Problem Set 4 posted, due on May 1, the last class meeting. I plan to post one more problem set to be due at the end final exam week.
(3/2) Problem Set 3 posted.
(2/9) Problem Set 2 posted.
(2/5) Pointers on this page to Stanley EC Vol 1 now refer to the 2nd edition. If you have the 1st edition, you may wish to consult the 2nd edition manuscript on Stanley's EC web page, which has an appendix listing material re-numbered between editions.
(1/28) Problem Set 1 now posted, see below.
(1/3) Welcome to Math 249!

Professor

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

Time and place

MWF 2-3 pm, Room 2 Evans Hall

Textbooks

The course will loosely follow

Richard Stanley, Enumerative Combinatorics, Vols. I (2nd ed) and II, Cambridge Univ. Press 1997, 2001, 2012

Among other useful information on Stanley's web page, linked above, you can find a PDF manuscript version of Volume I, 2nd edition.

I will give pointers to reading from Stanley for many of the lectures, and include a number of problems from Stanley in the homework assignments.

For some course topics you may also find the following helpful:

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.
Bruce Sagan, The Symmetric Group: Representations, Combinatorial Algorithms and Symmetric Functions (2nd ed), Springer, 2001.
Ian Macdonald, Symmetric functions and Hall polynomials (2nd ed), Oxford Univ. Press, 1995.

Homework and grading

Problem sets are below, after the list of lecture topics. I'll post new sets at irregular intervals, due about two weeks after posted. Grades will be based on homework; there will be no exams. To get an A in the course, you should do most of the probems, not skipping the harder ones.

Outline

Ordinary generating functions and enumeration of sets, mappings, multisets, distributions, permutations, words, lattice paths, trees, and other basic combinatorial objects.
Combinatorial species, exponential generating functions and cycle index. Combinatorial interpretation of Lagrange inversion.
Posets, lattices and incidence algebras. Mobius inversion. Geometric lattices and their characteristic polynomials. Brief discussion of polytopes, simplicial complexes and shellability.
Symmetric functions. Character theory of the symmetric groups S_n and general linear groups GL_n.
q-analogs in enumeration and symmetric function theory. Geometry and combinatorics of Hall-Littlewood polynomials and the Hall algebra.
q,t-analogs and Macdonald polynomials.

List of topics by lecture

I will update this list as the course proceeds. Pointers to Stanley, EC Vol 1 refer to the 2nd edition.

(1/21) Basic counting principles; ordinary generating functions; enumeration of words, permutations, sets and multisets. [Stanley 1.1-1.2]
(1/23) Formal power series. Sets and multisets continued.
(1/26) Binomial coefficient identities; binomial inversion. The `12-fold way.' Stirling numbers S(n,k). [Stanley 1.9]
(1/28) Signless Stirling numbers of the 1st kind c(n,k); ordinary generating functions for c(n,k) and S(n,k).
(1/30) Integer partitions. Partition identities. Combinatorial interpretation of Rogers-Ramanujan identities. [Stanley 1.8]
(2/2) Euler's pentagonal number identity and recurrence for p(n). Sylvester's identity. q-binomial and multinomial coefficients. [Stanley 1.7]
(2/4) q-Binomial Theorems and Cauchy's identity. [Stanley 1.8]
(2/6) Subspaces of (F_q)ⁿ. Descents of permutations; quasisymmetric expansion of (x₁ + x₂ + ···)ⁿ. [Stanley 7.19]
(2/9) Counting permutations by major index. [Stanley 1.4]
(2/11) Double partitions and symmetry of ∑_π q^inv(π) t^maj(π).
(2/13) Counting ordered rooted trees and other Catalan enumerations. [Stanley 1.5]
(2/18) Cayley's tree enumerator. Matrix-Tree Theorem. [Stanley 5.6]
(2/20) Matrix-Tree applications. Intro to species.
(2/23) Exponential generating function of a species; sum and product of species. [Stanley 5.1-2]
(2/25) Composition of species. Mixed ordinary and exponential generating functions. Examples: partitions, permutations, trees, exponential generating functions for S(n,k) and c(n,k).
(2/27) Counting trees using functional digraphs. Lagrange inversion formula from Cayley's tree enumerator. [Stanley 5.3-4]
(3/2) Counting structures of a species up to isomorphism. Cycle index.
(3/4) Decorated species and plethystic evaluation Z_F[A] of cycle indices.
(3/6) Plethysm and the cycle index for composite species.
(3/9) Species examples with computer demo: (i) connected graphs up to isomorphism, counted by number of vertices and edges; (ii) unrooted trees up to isomorphism.
(3/11) Posets and distributive lattices. [Stanley 3.1-3.5]
(3/13) Incidence algebras, Mobius function. Principle of Inclusion-Exclusion as an example of Mobius inversion. [Stanley 3.6-3.8]
(3/16) Classical (number theoretic) Mobius inversion. Chromatic polynomial as a characteristic polynomial. Mobius function of partition lattice Π_n from chromatic polynomial of the complete graph K_n. General formulas for the Mobius function of a lattice. [Stanley 3.9-3.10]
(3/18) Reduced incidence algebras. Incidence algebra interpretation of multiplication and composition of formal series. Mobius function of Π_n revisited.
(3/20) Order polynomials and reciprocity. Acyclic orientations and value χ_G(−1) of the chromatic polynomial of a graph. [Stanley 3.12, 3.15]
(3/30) Symmetric functions. Ordering on partitions. Monomial and elementary bases. [Stanley 7.1-7.4]
(4/1) Complete homogeneous and power-sum symmetric functions. Involution ω. [Stanley 7.5-7.8]
(4/3) Scalar product and Cauchy identities. Schur functions: combinatorial definition, symmetry, quasi-symmetric expansion. [Stanley 7.9, 7.10]
(4/6) RSK algorithm. [Stanley 7.11]
(4/8) Orthormality of Schur functions; ω(s_λ). [Stanley 7.12]
(4/10) Pieri formulas. Bialternant formula s_λ(x₁,...,x_n) = a_λ+δ/a_δ. [Stanley 7.15]
(4/13) Polynomial representations of GL_n and their characters. Bialternant interpreted as Weyl character formula. [Stanley Ch. 7 Appendix 2]
(4/15) Jacobi-Trudi formula for s_λ/μ. Jeu-de-taquin. Schensted insertion understood as rectification. [Stanley Ch. 7 Appendix 1]
(4/17) Statement of main theorem on jeu-de-taquin. Preservation of descent set; generalization to semi-standard tableaux. Computation of skew schur functions by rectification. Dual equivalence.
(4/20) Dual equivalence on straight shapes. Reduction to elementary dual equivalences.
(4/22) Exchange lemma for jeu-de-taquin on posets. Proof of main theorem on jeu-de-taquin. Yamanouchi tableaux and the Littlewood-Richardson rule.
(4/24) Characters of finite groups. Frobenius map, relation to cycle index of a species, isometry property. [Stanley 7.18]
(4/27) Irreducible characters of symmetric groups S_n. Plethystic substitution.
(4/29) Murnaghan-Nakayama rule. Definition of LLT polynomials.
(5/1) More on LLT, Hall-Littlewood and Macdonald polynomials.

Problem sets

Problem Set 1 on Lectures 1-4, due Friday Feb. 13. Here is the LaTeX source file for your convenience in case you want to compose your solutions in TeX. Updates: 2/5—added EC1 2nd ed numbering of Stanley exercises; fixed typos in 11(b). 2/27—fixed 1(c) to take account of cases in which the product converges to zero.
Problem Set 2 on Lectures 5-8, due Friday Mar. 6 (LaTeX source file).
Problem Set 3 on Lectures 9-16, due Monday Mar. 30 (LaTeX source file).
Problem Set 4 on Lectures 17-26, due Friday May 1 (LaTeX source file).
Problem Set 5 on Lectures 27-39, due Friday May 15 (LaTeX source file).