TR-2005-11

Matroid matching with Dilworth truncation

Márton Makai



Abstract

Let H=(V,E) be a hypergraph and let k \ge 1 and l \ge 0 be fixed integers. Let M be the matroid with ground-set E s.t. a set F \subseteq E is independent if and only if each X \subseteq V with k|X|-l \ge 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 Lovász' min-max formula 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).


Bibtex entry:

@techreport{egres-05-11,
AUTHOR = {Makai, M{\'a}rton},
TITLE = {Matroid matching with Dilworth truncation},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2005},
NUMBER = {TR-2005-11}
}


Last modification: 5.12.2018. Please email your comments to Tamás Király!