Ask Your Question

Maximal matching of a poset

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

daltop gravatar image


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

1 Answer

Sort by » oldest newest most voted

answered 2020-09-04 18:15:04 +0200

FrédéricC gravatar image

Maybe use the undirected Hasse diagram ?

sage: P=posets.PentagonPoset()                                                  
sage: G=P.hasse_diagram().to_undirected()                                       
sage: G.matching()                                                              
[(2, 3, None), (1, 4, None)]
edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools

1 follower


Asked: 2020-09-04 13:55:52 +0200

Seen: 274 times

Last updated: Sep 04 '20