*Wissenschaftliches Programm* *Liste der Vortragenden*

**Sektion 15**

Dienstag, 19.09.2000,
16.00–16.20 Uhr, WIL C 103

#### Bianca Spille, Otto-von-Guericke-Universität Magdeburg

The matching problem together with the optimization problem over the intersection of two matroids are in
some sense the hardest combinatorial optimization problems that are known to be solvable by polynomial
time algorithms.

In this talk, we study some connections between the matching problem and the intersection of
matroids. We characterize when the set of matchings in the graph K_{n} can be represented as the
intersection of a given number m of matroids in terms of necessary and sufficient conditions. This
description leads in a natural way to an IP-formulation of the introduced problem, which can be
solved by standard IP-solvers, for at least not too large values of n and m. We also present a
characterization of all graphs for which the set of matchings is the intersection of at most two matroids.
Although the matching problem is polynomially solvable and the rank quotient of any matching
independence system is always at least 1/2, the set of matchings can in general not be written as the
intersection of at most three matroids. Upper bounds on the number of matroids required
to represent the matchings on any graph with n nodes as the intersection of finitely many
matroids are studied. In fact, O() matroids can be constructed explicitely to yield such a
representation.

This is joint work with Robert T. Firla.