Maximal matching of a poset

asked 2020-09-04 13:55:52 +0100

daltop
13 ●3

Hi,

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.

edit retag flag offensive close merge delete

add a comment

sage: P=posets.PentagonPoset() sage: G=P.hasse_diagram().to_undirected() sage: G.matching() [(2, 3, None), (1, 4, None)]

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Maximal matching of a poset

1 Answer

Your Answer

Question Tools

Stats

Related questions

Maximal matching of a poset edit

1 Answer