×

zbMATH — the first resource for mathematics

An intersection theorem for supermatroids. (English) Zbl 0727.05016
The author generalizes the matroid intersection theorem to distributive supermatroids, a structure that extends the matroid to the partially ordered ground set. Distributive supermatroids are special cases of both supermatroids and greedoids, and they generalize polymatroids. This is the first good characterization proved for the intersection problem of an independence system where the ground set is partially ordered. The two partially ordered distributive supermatroids are defined on the same partially ordered set. The author also shows that the problem of finding the maximum common independent set of two supermatroids defined of different partially ordered sets contains the matroid matching problem as a special case.

MSC:
05B35 Combinatorial aspects of matroids and geometric lattices
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Dunstan, F.D.J; Ingleton, A.W; Welsh, D.J.A, Supermatroids, (), 72-122, Oxford
[2] Edmonds, J, Submodular functions, matroids, and certain polyhedra, (), 69-87
[3] Faigle, U, Geometries on partially ordered sets, J. combin. theory ser. B, 28, 26-51, (1980) · Zbl 0359.05018
[4] Korte, B; Lovász, L, Structural properties of greedoids, Combinatorica, 3-4, 359-374, (1983) · Zbl 0526.05018
[5] Korte, B; Lovász, L, Greedoids—a structural framework for the greedy algorithm, (), 221-243
[6] Lovász, L; Plummer, M.D, (), and Akadémiai Kiadó, Budapest
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.