2
$\begingroup$

In a graph, the class of all the sets of vertices that can be covered by some matching forms a matroid.

I wonder what kind of structure the class of all the matchings in a graph can have? Or does it not have any usual structure?

It seems to me that it is close to but not a matroid. Is it the reason to study the class of all the sets of vertices covered by some matching, instead of studying directly the class of all the matchings?

Thanks!

  • 0
    any $m$atching, not necessarily maximum/perfect.2012-11-10

1 Answers 1

5

I think the main issue here is what the ground set of the matroid ought to be. The matching matroid has ground set $V(G)$, while each matching is a subset of $E(G)$. Unfortunately, in general, the set of matchings is not the set of independent sets of a matroid. It is of course a family that is closed under taking subsets, but the augmentation axiom fails. For example, if $G$ is path of three edges, and $M_1$ is the matching consisting of the middle edge, and $M_2$ is the matching consisting of the two end edges, then $|M_2|>|M_1|$, but we cannot augment $M_1$ via an edge in $M_2$.

That is not to say that the set of matchings does not have nice properties, just that it is not a matroid. For example, there is this beautiful theorem of Edmond's that completely describes the convex hull of the set of matchings via linear inequalities.

  • 0
    Thanks! It looks like the set of all the matchings is just an [independence system](http://en.wikipedia.org/wiki/Matroid#Independent_sets), since an empty set is a matching, and any subset of a matching is still a matching. We don't know if there are other structures on it.2012-11-11