Characterizing Matchings as the Intersection of Matroids

Details Characterizing Matchings as the Intersection of Matroids Characterizing Matchings as the Intersection of Matroids

2002-12-17

arxiv.org/abs/math/0212235v2

Mathematics

Combinatorics

12 pages, 1 figure; to appear in Mathematical Methods of Operations Research, added references

Scientific paper

This paper deals with the problem of representing the matching independence system in a graph as the intersection of finitely many matroids. After characterizing the graphs for which the matching independence system is the intersection of two matroids, we study the function mu(G), which is the minimum number of matroids that need to be intersected in order to obtain the set of matchings on a graph G, and examine the maximal value, mu(n), for graphs with n vertices. We describe an integer programming formulation for deciding whether mu(G)<= k. Using combinatorial arguments, we prove that mu(n)is in Omega(loglog n). On the other hand, we establish that mu(n) is in O(log n / loglog n). Finally, we prove that mu(n)=4 for n=5,...,12, and mu(n)=5 for n=13,14,15.

Affiliated with

Also associated with

No associations

Rating

Characterizing Matchings as the Intersection of Matroids does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Characterizing Matchings as the Intersection of Matroids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Characterizing Matchings as the Intersection of Matroids will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-259508