Skip to Main content Skip to Navigation
Conference papers

Matroid matching with Dilworth truncation

Abstract : Let $H=(V,E)$ be a hypergraph and let $k≥ 1$ and$ l≥ 0$ be fixed integers. Let $\mathcal{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 $\mathcal{M}$ satisfies the double circuit property, thus the min-max formula of Dress and Lovász on the maximum matroid matching holds for $\mathcal{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)$.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 11:36:44 AM
Last modification on : Thursday, May 11, 2017 - 1:02:54 AM
Long-term archiving on: : Sunday, November 15, 2015 - 10:57:49 AM


Publisher files allowed on an open archive




Márton Makai. Matroid matching with Dilworth truncation. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.175-180, ⟨10.46298/dmtcs.3393⟩. ⟨hal-01184349⟩



Record views


Files downloads