Márton Makai
-
Matroid matching with Dilworth truncation
dmtcs:3393 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
-
https://doi.org/10.46298/dmtcs.3393
Matroid matching with Dilworth truncationArticle
Authors: Márton Makai 1
NULL
Márton Makai
1 Operations Research Department
Let H=(V,E) be a hypergraph and let k≥1 andl≥0 be fixed integers. Let M be the matroid with ground-set Es.t.a set F⊆E is independent if and only if each X⊆V with k|X|−l≥0 spans at most k|X|−l hyperedges of F. We prove that if H is dense enough, then M satisfies the double circuit property, thus the min-max formula of Dress and Lovász on the maximum matroid matching holds for M . Our result implies the Berge-Tutte formula on the maximum matching of graphs (k=1,l=0), generalizes Lovász' graphic matroid (cycle matroid) matching formula to hypergraphs (k=l=1) and gives a min-max formula for the maximum matroid matching in the 2-dimensional rigidity matroid (k=2,l=3).