most recent 30 from http://mathoverflow.net 2013-05-23T00:55:36Z http://mathoverflow.net/feeds/question/43844 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/43844/algorithm-to-find-an-acyclic-matching-on-a-poset Priyavrat Deshpande 2010-10-27T18:09:30Z 2010-10-27T18:44:20Z

<p>Are there algorithms / theorems to find an acyclic matching on the Hasse diagram of a poset. </p> <p>I am particularly interested in the face poset of a regular CW complex. Also, how to decide if the given acyclic matching is perfect (impossible to add one more vertex). Is there some structure on the set of all acyclic matchings ?</p>

http://mathoverflow.net/questions/43844/algorithm-to-find-an-acyclic-matching-on-a-poset/43847#43847 Dan Ramras 2010-10-27T18:44:20Z 2010-10-27T18:44:20Z

<p>You can start with a small matching and try to improve it. This paper of Patricia Hersch might be useful in this direction:</p> <p>Hersh, Patricia(1-IN) On optimizing discrete Morse functions. (English summary) Adv. in Appl. Math. 35 (2005), no. 3, 294–322. </p> <p>As for the last question, Chari and Joswig have a paper analyzing the space of all acyclic matchings. I don't know that the analysis is useful for the first two questions, though.</p> <p>Chari, Manoj K.(1-LAS); Joswig, Michael(D-TUB-IM) Complexes of discrete Morse functions. (English summary) Discrete Math. 302 (2005), no. 1-3, 39–51. </p>