Matroid matching with Dilworth truncation Original Research Article

Let image be a hypergraph and let image and image be fixed integers. Let image be the matroid with ground-set E s.t. a set image is independent if and only if each image with image spans at most image hyperedges of F. We prove that if H is dense enough, then image satisfies the double circuit property, thus Lovász’ min–max formula on the maximum matroid matching holds for image. Our result implies the Berge–Tutte formula on the maximum matching of graphs (image, image), generalizes Lovász’ graphic matroid (cycle matroid) matching formula to hypergraphs (image) and gives a min–max formula for the maximum matroid matching in the two-dimensional rigidity matroid (image, image).