Math 249 - Algebraic Combinatorics - Fall 2013
Lectures: Tuesday and Thursday 12:30pm-2:00pm, in 35 Evans
Lecturer: Lauren Williams
(office 913 Evans, e-mail williams@math.berkeley.edu)
Office Hours: Wednesday 2-3pm, Thursday 2-3pm, or by appointment.
Course description
This class will be an introduction to topological and
geometric combinatorics at the graduate
level, covering several general areas:
(1) Posets
(2) Simplicial complexes
(3) Matroids
(4) Polytopes
One of the main themes of the class will be the question
``To what extent do combinatorial properties of an
object determine its topology or geometry?"
For example, to what extent does the face lattice of a
simplicial or cell complex determine its homotopy type?
To what extent does the graph of a polytope determine
the polytope? And what kinds of combinatorial techniques
can we use to then understand the topology
of the object in question? Along the way we will
discuss interesting examples coming from posets,
polytopes, matroids, Coxeter groups, the Grassmannian
and flag varieties, etc.
Course Prerequisites
I will assume that student have background in graduate algebra
(such as 250A). It will also be helpful to have some exposure to
algebraic topology (215A), including topics such as homology and homotopy.
Textbooks
Required texts: Enumerative Combinatorics I, 2nd edition (Richard Stanley).
Recommended reading: Matroid Theory (James Oxley), Lectures on Polytopes (Gunter Ziegler).
Grading
Homework will be assigned every two weeks. Grading will be based
on homework (50%), and a presentation (10%) and final paper (40%) on a topic of your choice.
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 December 13.
Lectures
The following is a first approximation of the schedule for the course.
Lecture 1 (Aug. 29): Introduction of the main characters: simplicial complexes, posets, matroids, polytopes.
Lecture 2 (Sep. 3): Poset terminology, lattices, linear extensions.
Lecture 3 (Sep. 5): The incidence algebra, Mobius
inversion, and the Euler characteristic of the order complex.
Lecture 4 (Sep. 10): Shellability.
A shellable simplicial complex is homotopy equivalent to a wedge of spheres.
EL labelings.
Lecture 5 (Sep. 12): An EL labeling induces a shelling of the order complex.
EL labelings for distributive lattices.
Lecture 6 (Sep. 17): CW complexes and their face posets.
Lecture 7 (Sep. 19): Guest lecture by Michelle Wachs.
Lecture 8 (Sep. 24): Bruhat order and shellability.
Lecture 9 (Sep. 26): Grassmannians,
flag varieties, and Bruhat order.
Lecture 10 (Oct. 1): Matroids (axiom systems from independence,
bases, circuits).
Lecture 11 (Oct. 3): The GGMS theorem on matroid polytopes.
Lecture 12 (Oct. 8): Operations on matroids; applications
to matroid polytopes and the Tutte polynomial.
Lecture 13 (Oct. 10): The matroid stratification. Positroids and positroid polytopes.
Lecture 14 (Oct. 15): Oriented matroids and the matroid Grassmannian
(the MacPhersonian MacP(k,n)).
Lecture 15 (Oct. 17): Positively oriented matroids (POMs).
Realizability of POMs. MacP+(k,n).
Lecture 16 (Oct. 22): The face lattice of polytopes. The cyclic polytope;
the permutohedron.
Lecture 17 (Oct. 24): Face numbers of polytopes. H-vectors
of simplicial polytopes via shelling.
Lecture 18 (Oct. 29): No class (LKW out of town).
Lecture 19 (Oct. 31): Simple polytopes and their graphs; graph-associahedra.
Lecture 20 (Nov. 5):
The g-theorem (which characterizes face numbers of all f-vectors of simplicial polytopes). The cd-index.
Lecture 21 (Nov. 7): Discrete Morse theory.
Lecture 22 (Nov. 12): Flag matroids and Coxeter matroids.
Lecture 23 (Nov. 14):
TNN Grassmannian + toric geometry (Hood Chatham);
Parameterizing
TNN flag varieties (Emmanuel Tsukerman);
Shelling TNN flag varieties (Steven Karp).
Lecture 24 (Nov. 19):
Tutte polynomial (Bo Lin);
the categorification of Tutte/chromatic polynomials (Jeff Hicks);
flow polytopes
(Maryam Farahmand).
Lecture 25 (Nov. 21): Discrete Morse theory (Kim Dae Young);
the space
of tropically collinear points is shellable (Joe Kileel);
Gelfand-Serganova work (Josh Wen).
Lecture 26 (Nov. 26): Posets and Coxeter sequences (Evan Chen);
two poset polytopes (Qingyun Wu);
greedy algorithm for matroids (Henry Maltby).
Nov. 28: Thanksgiving (no lecture)
Lecture 27 (Dec. 3): Positroids and non-crossing partitions
(presented by Benson Au, Anastasia Chavez, and Jun Hong).
Lecture 28 (Dec. 5):
Eulerian posets (Moor Xu);
the hard Lefschetz theorem and polytopes (Ryan Thorngren);
how to shell a monoid (Justin Chen).
FINAL PROJECT DUE (December 13)
Problem Sets
Problem Set 1 (due September 19)
Problem Set 2 (due October 3)
Problem Set 3 (due October 17)
Problem Set 4 (due October 31)
Problem Set 5 (due November 19)
Suggestions for final projects
Ideas for projects