Márton Makai - Matroid matching with Dilworth truncation

dmtcs:3393 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3393
Matroid matching with Dilworth truncationArticle

Authors: Márton Makai 1

  • 1 Operations Research Department

Let H=(V,E) be a hypergraph and let k1 andl0 be fixed integers. Let M be the matroid with ground-set Es.t.a set FE is independent if and only if each XV with k|X|l0 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).


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: matroid matching,Dilworth truncation,double circuit property,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

1 Document citing this article

Consultation statistics

This page has been seen 219 times.
This article's PDF has been downloaded 376 times.