Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question

2 Answers 2

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|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: http://arxiv.org/abs/1303.6422

share|improve this answer

Your Answer

 
discard

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.