Poset matching---a distributive analog of independent matching (Q685701): Difference between revisions

If \((P,\leq)\) is a finite poset, \({\mathcal F}={\mathcal F}(P)\) is the lattice of order ideals and an hereditary system \(D(P)\) consists of a collection of order ideals \({\mathcal I}\) (called independent) satisfying: \(0 \in{\mathcal I}\), \(A \leq B \in{\mathcal I}\), \(A \in{\mathcal F}\) implies \(A \in {\mathcal I}\). A poset- (or distributive super-)matroid is a \(D(P)\) such that T 2.1. giving several equivalent conditions (e.g. (2) \(A\), \(B \in{\mathcal I}\) and \(| B |>| A |\) implies \((B-A)\) contains a minimal element \(b\) such that \(A \cup \{b\} \in{\mathcal I})\) holds. The study of poset matroids is among possible generalizations of matroid theory. The authors demonstrate further how useful this generalization is in a variety of ways. The key result is a (cardinality) poset matching algorithm matching independent ideals of \(D(P)\) to those of \(D(Q)\) terminating after \(O(N^ 3)\) appeals to the independence oracles where \(N=\max \bigl\{ | P |,| Q | \bigr\}\). Specializations of \(P\) and \(Q\) provide well-known results, including algorithms, while other equally well-known results can be made consequences of the same algorithm. Thus analogs and generalizations of these results are obtained, including an interpretation of the Dilworth completion of a poset matroid in terms of matchings which is used in reducing weighted poset matching to weighted matroid intersection. Along with a selection of examples, the techniques employed provide promising insights into the working of the theory at its present state of development.