Math 701: Topological Combinatorics

Welcome to the course home page for Math 701, Topological Combinatorics. Class meets Mondays and Wednesdays, 2:30-3:45pm in Rawles Hall 104. The main purpose of this web site is to list course topics and days we'll cover them -- for instance, to help auditors decide which days to come.

Text: There is no required text for this course, but there are two recommended ones: Using the Borsuk-Ulam Theorem, by Jiri Matousek, and Combinatorics and Commutative Algebra, by Richard Stanley. I actually recommend that students each buy one of these two books and share with each other -- I'd suggest buying the former if one is most interested in connections to topology and/or one is at all shaky on the prerequisite topological background, or buying the latter if one is more interested in connections to algebra. The latter is aimed at a much more advanced audience.

Homework: Students are expected to submit at least three homeworks for grading during the semester; students may submit as many homeworks as they wish, and then the three highest scores will be counted. Students are also encouraged to go through their notes filling in details when I make claims in class without proof. Papers will be given scores of S (for completely correct proof), S+ (for completely correct proof with excellent exposition), S- (for proof with small gap) or N (for proof with more substantial error). Students earning an average of S on their top three papers will receive an A for homework, so are likely to receive an A in the course as long as they come to class regularly, etc. Below is a list of homework assignments so far (with widely varying levels of difficulty):

1. Prove that the order complex of the face poset of a simplicial complex is isomorphic to the first barycentric subdivision of the simplicial complex.
2. Prove that the k-skeleton of a d-simplex is shellable.
3. Prove that all geometric lattices are EL-shellable and that the descending chains are in 1-1 correspondence with the NBC bases of the associated matroid. (You are welcome to consult Bjorner's paper proving this result, and write up solution in your own words; a sketch of many of the main ideas was also given in class.)
4. Prove that the chromatic polynomial of a graph equals the characteristic polynomial of the intersection lattice of the associated graphic arrangement. (You are welcome to consult C. Athanasiadis's paper. Hint: prove that both polynomials count points in the complement of the arrangement when working over a finite field F_q, where q is the variable in the polynomial, then show result extends from prime powers to all q.)
5. Use discrete Morse theory to prove that shellable simplicial complexes are homotopy equivalent to wedges of spheres.
6. Fill in details in the one case in the proof of the homotopy type of not 2-connected graph complexes which was left as an exercise (i.e. for one portion of the discrete Morse theory proof that fibres are contractible).

Schedule of lecture topics:

Mon. Jan. 9 -- posets and Moebius functions: terminology and examples

Wed. Jan. 11 -- properties of Moebius functions: equivalence to order complex reduced Euler characteristic, multiplicativeness, etc.; notion of sign reversing involution

Mon. Jan. 16 -- no class -- Martin Luther King Day

Wed. Jan. 18 -- proof of Crapo's Closure Lemma by sign reversing involution; notion of shellability

Mon. Jan. 23 -- quick review of some terminology from topology; Thm: a shellable simplicial complex is homotopy equivalent to a wedge of spheres

Wed. Jan. 25 -- lexicographic shellability (cf. Bjorner; Bjorner and Wachs); Thm: EL-labelling induces order complex shelling

Mon. Jan. 30 -- Thm (Bjorner): partition lattice is EL-shellable; counting descending chains to compute Moebius function; description of EL-labelling for distributive lattices

Wed. Feb. 1 -- Terminology/notions/examples from matroid theory

Mon. Feb. 6 -- background on matroids (cont); Thm: geometric lattices are EL-shellable

Wed. Feb. 8 -- Moebius inversion on finite posets; Moebius functions on shellable, graded posets alternate in sign

Mon. Feb. 13 -- T. Zaslavsky's theorems on region counting in a real hyperplane arrangement

Wed. Feb. 15 -- Complexity theory lower bound for k-equal problem via linear decision trees (cf. Bjorner, Lovasz and Yao)

Mon. Feb. 20 -- quick, very informal review of (simplicial and singular) cohomology; finish linear decision trees (using Goresky-MacPherson formula to obtain bound on tree depth); very quick discussion of characteristic polynomial and its relation to graph chromatic polynomial

Wed. Feb. 22 -- description of the Orlik-Solomon Algebra, i.e. a very nice presentation for the cohomology of the complement of a complex hyperplane arrangement; begin f-vectors and Stanley-Reisner rings

Mon. Feb. 27 -- computing h-vectors via shelling; Dehn-Sommerville equations; relationship between face numbers and Hilbert function of Stanley-Reisner ring

Wed. March 1 -- Upper Bound Theorem for spheres (due to Stanley)

Mon. March 6 -- finish proving properties of M-vectors used last time; also prove neighborliness of cyclic polytopes

Wed. March 8 -- review localization and local cohomology

Mon. March 13 -- SPRING BREAK

Wed. March 15 -- SPRING BREAK

Mon. March 20 -- Hochster's Theorem and Reisner's Theorem

Wed. March 22 -- finish Hochster's Theorem; brief discussion of Gorenstein face rings

Mon. March 27 -- brief discussion of the g-theorem

Note: on March 27 and 29, Ed Swartz will give seminar talks on his recent generalizations of some of the inequalities in the g-theorem and on face numbers of (triangulations of) manifolds

Wed. March 29 -- 45 minute guest lecture by Ed Swartz (on commutative algebra used in his March 27 seminar talk); begin discrete Morse theory

Mon. April 3 -- discrete Morse theory (cont)

Wed. April 5 -- discrete Morse theory (cont)

Mon. April 10 -- discrete Morse theory (cont)

Wed. April 12 -- application to not 2-connected graph complexes

Mon. April 17 -- finish not 2-connected graph complexes

Wed. April 19 -- lexicographic discrete Morse functions for poset order complexes

Mon. April 24 -- quick review of some basic representation theory; explicit construction of the irreducible representations of the symmetric group as Specht modules

Wed. April 26 -- very brief discussion of group actions on posets, along with the example of computing the S_n module structure for the (top) homology of the rank-selected Boolean algebra as a Specht module of ribbon shape

Some Possible Further Topics (we would have covered, if there'd been more time): group actions on posets; construction of explicit homology bases; nerve theorem; application to computing Betti numbers of monomial ideals via homology of LCM lattices; lower bound on chromatic number of Kneser graphs via the Borsuk-Ulam Theorem.

Return to my homepage

Return to Indiana University Math Department Homepage