Fractional matroid matching

Dion Gijswijt, Universiteit van Amsterdam

The matroid matching problem (for linear matroids) is the following: Given a collection of pairs of vectors, what is the maximum number of pairs whose union is linearly independent? Lovász gave a polynomial time algorithm for this linear case, but for general matroids the problem is not polynomial time solvable. Also, for linear matroids, no polynomial algorithm is known for finding a matching of maximum weight, and no polyhedral characterization is know. This motivated Vande Vate to introduce fractional matroid matchings, which are hoped to be more tractable, while still containing interesting special cases such as matroid intersection. The goal of the talk is to show that the corresponding polytope has many nice properties, for example: it is half-integral and the separation problem is in NP ∩ co-NP. This suggests that it might be possible to separate/optimize in polynomial time, but this remains an open problem.

back to EIDMA Seminar Combinatorial Theory announcements