Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

Maximal matching of a poset


I would like to know how to find a maximal 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.

A matching of a poset is the same as a matching of its Hasse Diagram. I thought about using the matching() function for graphs, however, it seems that the Hasse diagram of a poset is a Digraph for Sage and so the matching function does not work.

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

Any help would be appreciated.