Zurück zu den Preprints des Jahres 2000


Matching as the Intersection of Matroids

by Firla, Robert T., Spille, Bianca.

Series: 2000-17, Preprints

90C10 Integer programming
90C27 Combinatorial optimization
05B35 Matroids, geometric lattices
05C70 Factorization, matching, partitioning, covering and packing

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

matching, matroid intersection, circuit-graph