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 <>
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

  • HAL Id : hal-01184349, version 1

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. ⟨hal-01184349⟩

Share

Metrics

Record views

84

Files downloads

757