5
$\begingroup$

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 ?

$\endgroup$

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

Let me mention the random approach by Bruno Benedetti and Frank Lutz: http://arxiv.org/abs/1303.6422

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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