Math 249 - Algebraic Combinatorics - Spring 2010

Lectures: Tuesday and Thursday 11am-12:30pm, in 5 Evans

Lecturer: Lauren Williams (office 913 Evans, e-mail williams@math.berkeley.edu)

Office Hours: Wednesday 11am-12:30pm, or by appointment.

Course description

This class will be an introduction to combinatorics at the graduate level, covering four general areas:
(1) enumeration (ordinary and exponential generating functions)
(2) order (posets, lattices, incidence algebras)
(3) geometric combinatorics (simplicial complexes, polytopes, matroids, hyperplane arrangements)
(4) symmetric functions, tableaux, and the connection to representation theory.

Textbooks

Required texts: Enumerative Combinatorics I and II (Richard Stanley).
Recommended reading: Young Tableaux (William Fulton), The Symmetric Group (Bruce Sagan), Lectures on Polytopes (Gunter Ziegler).

Homework will be assigned every two weeks. Grading will be based on homework (50%) and a final paper (50%). No late homework will be accepted. Also, if you work with others on the homework, you must write up your solutions independently, and list the names of the students you worked with. The final paper is due on May 7.

Lectures

• Lecture 1 (Jan. 19): Begin enumeration (generating functions)
• Lecture 2 (Jan. 21): Rational (ordinary) generating functions
• Lecture 3 (Jan. 26): Exponential generating functions
• Lecture 4 (Jan. 28): Lagrange Inversion and enumeration of trees
• Lecture 5 (Feb. 2): Partitions and their generating functions. Start Matrix-Tree Theorem.
• Lecture 6 (Feb. 4): Matrix-Tree Theorem.
• Lecture 7 (Feb. 9): The Lindstrom-Gessel-Viennot Lemma.
• Lecture 8 (Feb. 11): Begin studying order (posets, lattices)
• Lecture 9 (Feb. 16): The incidence algebra and Mobius inversion.
• Lecture 10 (Feb. 18): Finish Mobius functions. Poset topology.
• Lecture 11 (Feb. 23): Posets coming from geometry: flag varieties and the Bruhat order.
• Lecture 12 (Feb. 25): More on flag varieties, including rank-generating functions and Mobius functions.
• Lecture 13 (March 2): Begin geometric combinatorics: hyperplane arrangements.
• Lecture 14 (March 4): The intersection poset of a hyperplane arrangement
• Lecture 15 (March 9): Hyperplane arrangements and matroids
• Lecture 16 (March 11): Introduction to polytopes
• Lecture 17 (March 16): Simple polytopes; go over homework.
• Lecture 18 (March 18): No lecture.
• Spring Recess (March 22-26)
• Lecture 19 (March 30): Begin studying symmetric functions: monomial and elementary symmetric functions
• Lecture 20 (April 1): Homogenous symmetric functions and Schur functions
• Lecture 21 (April 6): Introduction to the representation theory of finite groups.
• Lecture 22 (April 8): Analysis of representations of S3; characters of representations.
• Lecture 23 (April 13): Construction of the irreducible representations of Sn using Specht modules.
• Lecture 24 (April 15): Proof that the Specht modules are irreducible.
• Lecture 25 (April 20): Power sum symmetric functions. Inner product on symmetric functions.
• Lecture 26 (April 22): The RSK Algorithm and symmetric functions.
• Lecture 27 (April 27): From class functions of Sn to symmetric functions via the Frobenius characteristic.
• Lecture 28 (April 29): Schur functions, and the characters of the irreducible representations of Sn.
• FINAL PROJECT DUE (May 7)
• Problem Sets

• Problem Set 1 (due February 11)
• Problem Set 2 (due February 25)
• Problem Set 3 (due March 11)
• Problem Set 4 (due April 8)
• Problem Set 5 (due April 27)