Course control number: 55053

Professor: Mark Haiman
Office hours: W 11:00am-12:30pm
E-mail:
Office: 771 Evans
Phone: (510) 642-4318

GSI: Shahed Sharif
Office Hours: Tues 11am-12pm, Room 1093 Evans

Syllabus: Introduction to combinatorics at the graduate level, covering four general areas: (I) enumeration (ordinary and exponential generating functions), (II) order (posets, lattices, incidence algebas), (III) geometric combinatorics (hyperplane arrangements, simplicial complexes, polytopes), (IV) symmetric functions, tableaux and representation theory.

Prerequisites: Math 250A or equivalent algebra background

Required text: Richard P. Stanley, Enumerative Combinatorics, Vols. I & II. Cambridge Univ. Press 1999, 2000.

Recommended additional reading:

• 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, New York 2001.
• Günter M. Ziegler, Lectures on Polytopes. Birkhäuser Verlag, 2000.

Homework and grading: Grading will be based entirely on homework.  I'll try to give several problems on the topic of each lecture.  You may hand in problems for grading up to 2 weeks after they are assigned (except 1 week for the last two lectures).
To earn an A, you should do approximately 3 problems per week.  Harder problems count a bit more, easy problems or ones with answers in the book count less.  You are welcome to turn in more than the required number of problems, but I will ask the GSI to correct additional problems only if he has time.

Lecture topics and problems:

• Lecture 1 - Formal power series; ordinary generating functions (Stanley Ch. 1).  Problems
• Lecture 2 - The 12-fold way; Stirling numbers.  Problems
• Lecture 3 - Eulerian numbers; partition enumeration.  Problems
• Lecture 4 - Partitions cont'd; q-binomial coefficients.  Problems
• Lecture 5 - q-binomial theorem; pentagonal number theorem and Rogers-Ramanujan identities.  Problems
• Lecture 6 - Part I: q-Eulerian polynomials.  Part II: Exponential generating functions (Stanley Ch. 5).  Problems
• Lecture 7 - More on exponential generating functions.  Problems
• No lecture Thursday, Feb. 12, but here are some extra problems.
• Lecture 8 - Tree counting and Lagrange inversion (Stanley 5.4).  Problems
• Lecture 9 - I: Lagrange inversion cont'd.  II: Intro to Matrix-Tree theorem (Stanley 5.6).  Problems
• Lecture 10 - Matrix-Tree theorem and Eulerian walks.  Problems
• Lecture 11 - The Gessel-Viennot theorem.  Problems
• Lecture 12 - Introduction to symmetric functions (Stanley Ch. 7).  Problems (corrected 3(b) on 3/29)
• Lecture 13 - Bases for the ring of symmetric polynomials.  Problems
• Lecture 14 - Plethystic/lambda-ring notation.  Problems
• Lecture 15 - Schur functions.  Problems
• Lecture 16 - Schur functions continued.  Problems; Hints for problem 2 (corrected hint (a) on 4/11)
• Lecture 17 - Bi-alternants and the hook formula.  Problems (corrected 3(a) on 4/6)
• Lecture 18 - Skew Schur functions; intro to jeu-de-taquin.  Problems.  For the approach to jeu-de-taquin that I will be using, you may find Sagan's book and this article helpful.
• Lecture 19 - Jeu-de-taquin and dual equivalence.  Problems
• Lecture 20 - Fundamental theorems of jeu-de-taquin; Littlewood-Richardson rule.  Problems
• Lecture 21 - I: RSK correspondence. II: Intro to representations of finite groups.  Problems (corrected problem 2 on 4/21)
• Lecture 22 - Characters of finite groups.  Problems
• Lecture 23 - Characters of the symmetric groups.  Problems
• Lecture 24 - Murnaghan-Nakayama rule.  Problems
• Lecture 25 - Constructing irreducible representations.  Problems (corrected problem 1 on 5/6)
• Lecture 26 - Posets and incidence algebras (Stanley, Ch. 3).  Problems
• Lecture 27 - Lattices.  Problems
• Lecture 28 - Geometric lattices and hyperplane arrangements.  Problems
• Lecture 29 - Athanasiadis' trick; Eulerian posets and simplicial complexes.  Problems
• Lecture 30 - f-vectors, h-vectors, and Stanley's Lower Bound Theorem.