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

https://hal.inria.fr/hal-01184349
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

File

dmAE0135.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

34

Files downloads

492