Zurück zu den Preprints des Jahres 2000


2000-17

Matching as the Intersection of Matroids

by Firla, Robert T., Spille, Bianca.


Series: 2000-17, Preprints

MSC:
90C10 Integer programming
90C27 Combinatorial optimization
05B35 Matroids, geometric lattices
05C70 Factorization, matching, partitioning, 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