
handle: 10054/6891
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.
finite poset, Theorem, Combinatorial aspects of matroids and geometric lattices, poset matching algorithm, Theoretical Computer Science, Algorithm, Combinatorics of partially ordered sets, poset matroids, transversal, Transversal (matching) theory, matroid, Discrete Mathematics and Combinatorics, matchings, Partially Ordered Sets
finite poset, Theorem, Combinatorial aspects of matroids and geometric lattices, poset matching algorithm, Theoretical Computer Science, Algorithm, Combinatorics of partially ordered sets, poset matroids, transversal, Transversal (matching) theory, matroid, Discrete Mathematics and Combinatorics, matchings, Partially Ordered Sets
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
