UC Davis Mathematics

Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Computing optimal discrete Morse functions

Algebra & Discrete Mathematics

Speaker: Michael Joswig, TU Darmstadt and MSRI
Location: 1147 MSB
Start time: Fri, Sep 29 2006, 12:10PM

Morse matchings capture the essential structural information of discrete Morse functions, as introduced by Forman. We show that computing optimal Morse matchings is NP-hard and give an integer programming formulation for the problem. Then we present polyhedral results for the corresponding polytope and report on computational results. For the purpose of understanding the talk no knowledge in either classical or discrete Morse theory is assumed. (Joint work with Marc E. Pfetsch (ZIB Berlin)).