00-17
Matching as the Intersection of Matroids
by Firla, Robert T.; Spille, Bianca
Preprint series: 00-17, Preprints
- MSC:
- 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.