Characterizing matchings as the intersection of matroids

Sándor P. Fekete (), Robert T. Firla () and Bianca Spille ()

Mathematical Methods of Operations Research, 2003, vol. 58, issue 2, 319-329

Abstract: 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 μ(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 logn). On the other hand, we establish that μ(n)∈O(logn/ log logn). Finally, we prove that μ(n)=4 for n=5,…,12, and sketch a proof of μ(n)=5 for n=13,14,15. Copyright Springer-Verlag 2003

Keywords: matching; matroid intersection; 05B35; 05C70; 90C27 (search for similar items in EconPapers)
Date: 2003
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1007/s001860300301 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:58:y:2003:i:2:p:319-329

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s001860300301

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().