Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
When you say "matching", do you mean "partial (but potentially perfect) matching" or "only perfect matching"? –  Austin Mohr Nov 10 '12 at 20:36
    
any matching, not necessarily maximum/perfect. –  Tim Nov 10 '12 at 20:38

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
Thanks! It looks like the set of all the matchings is just an independence system, 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. –  Tim Nov 11 '12 at 20:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.