MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Are there algorithms / theorems to find an acyclic matching on the Hasse diagram of a poset.

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 ?

share|cite|improve this question
up vote 5 down vote accepted

You can start with a small matching and try to improve it. This paper of Patricia Hersch might be useful in this direction:

Hersh, Patricia(1-IN) On optimizing discrete Morse functions. (English summary) Adv. in Appl. Math. 35 (2005), no. 3, 294–322.

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.

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.

share|cite|improve this answer
Thank you very much. – Priyavrat Deshpande Oct 27 '10 at 18:49

Let me mention the random approach by Bruno Benedetti and Frank Lutz:

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.