Poset matching---a distributive analog of independent matching
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.
- A matroid generalization of a theorem of Mendelsohn and Dulmage
- A weighted matroid intersection algorithm
- An intersection theorem for supermatroids
- Dependence relations in a semi-modular lattice
- Geometries on partially ordered sets
- scientific article; zbMATH DE number 3904604 (Why is no real title available?)
- scientific article; zbMATH DE number 4025456 (Why is no real title available?)
- scientific article; zbMATH DE number 4027489 (Why is no real title available?)
- scientific article; zbMATH DE number 3534506 (Why is no real title available?)
- scientific article; zbMATH DE number 3558962 (Why is no real title available?)
- scientific article; zbMATH DE number 3600054 (Why is no real title available?)
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- Independence Spaces and Combinatorial Problems
- Matching Theory for Combinatorial Geometries
- Matroid Intersection
- Optimal matchings in posets
- Rado's theorem for polymatroids
- The greedy algorithm for partially ordered sets
- Transversals and matroid partition
- A note on order preserving matchings
- Matroids on partially ordered sets
- Antimatroids induced by matchings
- $n!$ matchings, $n!$ posets
- Matroids on convex geometries: subclasses, operations, and optimization
- Optimal matchings in posets
- On D-complementation
- Matroids on convex geometries (cg-matroids)
- Rank functions of strict cg-matroids
This page was built for publication: Poset matching---a distributive analog of independent matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685701)
