Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, January 14, 2003 - 4:30pm

Patricia Hersh

University of Michigan

Location

University of Pennsylvania

DRL 4N30

Forman introduced discrete Morse theory as a tool for studying CW-complexes by collapsing them onto smaller, simpler-to-understand complexes of critical cells. Chari provided a combinatorial reformulation based on acyclic matchings for their face posets. In joint work with Eric Babson, we showed how to construct a discrete Morse function with a fairly small (but typically not optimal) number of critical cells for the order complex of any finite poset from any lexicographic order on its saturated chains. I will discuss this construction as well as two more recent results about how to improve a discrete Morse function by cancelling pairs of critical cells. A key ingredient will be a correspondence between gradient paths in poset "lexicographic discrete Morse functions" and reduced expressions for permutations. As an application, in joint work with Volkmar Welker, we construct a discrete Morse function for graded monoid posets which yields upper bounds on Poincare' series coefficients for affine semigroup rings (by way of the Morse inequalities). These bounds are determined by the degree of a Gr\"obner basis for the toric ideal of syzygies and related data. I will begin with a brief review of discrete Morse theory.