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