Poset matching—a distributive analog of independent matching. (English) Zbl 0783.05037
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.
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.
Reviewer: J.Neggers (Tuscaloosa)
MSC:
| 05B35 | Combinatorial aspects of matroids and geometric lattices |
| 05D15 | Transversal (matching) theory |
| 06A07 | Combinatorics of partially ordered sets |
References:
| [1] | Aigner, M.; Dowling, T. A., Matching theory for combinatorial geometries, Trans. Amer. Math. Soc., 158, 231-245 (1971) · Zbl 0218.05013 |
| [2] | Brualdi, R. A., Introduction to matching theory, (White, N., Combinatorial Geometries (1987), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 53-71 · Zbl 0631.05013 |
| [3] | Dilworth, R. P., Dependence relations in a semimodular lattice, Duke. Math. J., 11, 575-587 (1944) · Zbl 0060.06101 |
| [4] | Dunstan, F. D.J.; Ingleton, A. W.; Welsh, D. J.A., Supermatroids, (Proc. Conf. Comb. Math. (1972), Math. Inst: Math. Inst Oxford), 72-122 |
| [5] | Edmonds, J.; Fulkerson, D. R., Transversals and matroid partition, J. Res Nat. Bur. Standards, 69B, 147-153 (1965) · Zbl 0141.21801 |
| [6] | Edmonds, J., Submodular functions, matroids, and certain polyhedra, (Guy, R., Combinatorial Structures and their Applications (1970), Gordon and Breach: Gordon and Breach New York), 69-87 · Zbl 0268.05019 |
| [7] | Edmonds, J., Matroid intersection, Ann. Discrete Math., 4, 39-49 (1979) · Zbl 0416.05025 |
| [8] | Faigle, U., The greedy algorithm for partially ordered sets, Discrete Math., 28, 153-159 (1979) · Zbl 0435.06003 |
| [9] | Faigle, U., Geometries on partially ordered sets, J. Combin. Theory Ser. B, 28, 26-51 (1980) · Zbl 0359.05018 |
| [10] | Faigle, U., Optimal matchings in posets, European J. Combin., 4, 295-303 (1983) · Zbl 0537.06003 |
| [11] | Faigle, U., Matroids on ordered sets and the greedy algorithm, Ann. Discrete Math., 19, 115-128 (1984) · Zbl 0567.05016 |
| [12] | Faigle, U., Matroids in combinatorial optimization, (White, N., Combinatorial Geometries (1987), Cambridge University Press: Cambridge University Press Cambridge), 161-210 · Zbl 0632.05018 |
| [13] | Frank, A., A weighted matroid intersection algorithm, J. Algorithms, 2, 328-336 (1981) · Zbl 0484.05025 |
| [14] | Kundu, S.; Lawler, E. L., A matroid generalization of a theorem of Mendelsohn and Dulmage, Discrete Math., 4, 159-163 (1973) · Zbl 0249.05017 |
| [15] | Lawler, E. L., Combinatorial Optimization: Networks and Matroids (1976), Holt, Rinehart, and Winston: Holt, Rinehart, and Winston New York · Zbl 0358.68059 |
| [16] | McDiarmid, C. J.H., Rado’s theorem for polymatroids, Math. Proc. Cambridge Philos. Soc., 78, 263-281 (1975) · Zbl 0321.05028 |
| [17] | Perfect, H., Independence spaces and combinatorial problems, Proc. London Math. Soc., 19, 17-30 (1969) · Zbl 0176.28302 |
| [18] | Schrijver, A., Matroids and Linking Systems (1978), Math. Centre Tracts 88: Math. Centre Tracts 88 Amsterdam · Zbl 0386.05020 |
| [19] | Tardos, E., An Intersection theorem for supermatroids, J. Combin. Theory Ser. B, 50, 150-159 (1990) · Zbl 0727.05016 |
| [20] | Welsh, D. J.A., Matroid Theory (1976), Academic Press: Academic Press New York · Zbl 0343.05002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
