Revision history [back]

Hi, Is there a function to compute the maximal acyclic matching (defined below) of a given finite poset?

 A matching  M in a poset X is a subset M of X x X such that:
   1) if (x, y) is in M, then x is an immediate predecessor of y (x<y and there is no element z such that x<z<y)
   2) each element x of X belongs to at most one element in M.

In order to represent the matching on the associated Hasse Diagram of the poset, we just reverse the arrows which are not in the matching. The matching is acyclic if the matching represented on its Hasse Diagram is acyclic.

By maximal matching I mean one with the maximal number of elements.

Any help would be appreciated.

Hi, Is there a function to compute the maximal acyclic (Morse) matching (defined below) of a given finite poset?

 A matching  M in a poset X is a subset M of X x X such that:
   1) if (x, y) is in M, then x is an immediate predecessor of y (x<y and there is no element z such that x<z<y)
   2) each element x of X belongs to at most one element in M.

In order to represent the matching on the associated Hasse Diagram of the poset, we just reverse the arrows which are not in the matching. The matching is acyclic (Morse) if the matching represented on its Hasse Diagram is acyclic.

By maximal matching I mean one with the maximal number of elements.

Any help would be appreciated.