DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Matroid matching with Dilworth truncation

Márton Makai

Abstract


Let H=(V,E) be a hypergraph and let k≥1 and l≥0 be fixed integers. Let M be the matroid with ground-set E s.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).

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional