Characterizing matchings as the intersection of matroids

Characterizing matchings as the intersection of matroids

0.00 Avg rating0 Votes
Article ID: iaor20051031
Country: Germany
Volume: 58
Issue: 2
Start Page Number: 319
End Page Number: 329
Publication Date: Jan 2003
Journal: Mathematical Methods of Operations Research (Heidelberg)
Authors: , ,
Keywords: matroids
Abstract:

This paper deals with the problem of representing the matching independent system in a graph as the intersection of finitely many matroids. After characterising the graphs for which the matching independence system is the intersection of two matroids, we study the function μ(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, μ(n), for graphs with n vertices. We describe an integer programming formulation for deciding whether μ(G) ≤ k. Using combinatorial arguments, we prove that μ(n) ∈ ω(log log n). On the other hand, we establish that μ(n) ∈ O(log n/log log n). Finally, we prove that μ(n) = 4 for n = 5, …, 12, and sketch a proof of μ(n) = 5 for n = 13, 14, 15.

Reviews

Required fields are marked *. Your email address will not be published.