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