Matching as the Intersection of Matroids

by Firla, Robert T.; Spille, Bianca


Preprint series: 00-17, Preprints

90C10 Integer programming
90C27 Combinatorial optimization
05B35 Matroids, geometric lattices, See also {52B40, 90C27}
05C70 Factorization, matching, covering and packing


Abstract: The set of matchings in a graph is an independence system and, hence, the intersection of finitely many matroids. We are interested in lower and upper bounds on the number of matroids needed to represent it. We characterize the graphs for which the set of matchings is the intersection of two matroids and show that the set of matchings on $K_5$ is not the intersection of at most three matroids. Furthermore, we prove upper bounds on the number of matroids.

Keywords: matching, matroid intersection, circuit-graph

Notes: Supported by a ``Gerhard-Hess-Forschungsf rderpreis\'\' (WE 1462/2-2) of the German Science Foundation (DFG) awarded to R. Weismantel.

The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster