Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

The intersection of a matroid and a simplicial complex


Authors: Ron Aharoni and Eli Berger
Journal: Trans. Amer. Math. Soc. 358 (2006), 4895-4917
MSC (2000): Primary 05B40
Published electronically: June 19, 2006
MathSciNet review: 2231877
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A classical theorem of Edmonds provides a min-max formula relating the maximal size of a set in the intersection of two matroids to a ``covering" parameter. We generalize this theorem, replacing one of the matroids by a general simplicial complex. One application is a solution of the case $ r=3$ of a matroidal version of Ryser's conjecture. Another is an upper bound on the minimal number of sets belonging to the intersection of two matroids, needed to cover their common ground set. This, in turn, is used to derive a weakened version of a conjecture of Rota. Bounds are also found on the dual parameter--the maximal number of disjoint sets, all spanning in each of two given matroids. We study in detail the case in which the complex is the complex of independent sets of a graph, and prove generalizations of known results on ``independent systems of representatives" (which are the special case in which the matroid is a partition matroid). In particular, we define a notion of $ k$-matroidal colorability of a graph, and prove a fractional version of a conjecture, that every graph $ G$ is $ 2\Delta(G)$-matroidally colorable.

The methods used are mostly topological.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 05B40

Retrieve articles in all journals with MSC (2000): 05B40


Additional Information

Ron Aharoni
Affiliation: Department of Mathematics, Technion, Israel Institute of Technology, Haifa, Israel 32000
Email: ra@tx.technion.ac.il

Eli Berger
Affiliation: Department of Mathematics, Princeton University, Princeton, New Jersey 08544 – and – Department of Mathematics, Technion, Israel Institute of Technology, Haifa, Israel 32000

DOI: http://dx.doi.org/10.1090/S0002-9947-06-03833-5
PII: S 0002-9947(06)03833-5
Keywords: Matroids, topology, Isr, Edmonds' theorem, Ryser's conjecture, Rota's conjecture
Received by editor(s): September 23, 2003
Received by editor(s) in revised form: September 3, 2004
Published electronically: June 19, 2006
Additional Notes: The research of the first author was supported by grants from the Israel Science Foundation, the M. & M.L. Bank Mathematics Research Fund and the fund for the promotion of research at the Technion
The research of the second author was supported by the National Science Foundation, under agreement No. DMS-0111298. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the view of the National Science Foundation.
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.