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).
Grading
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)