Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

The intersection of a matroid and a simplicial complex
HTML articles powered by AMS MathViewer

by Ron Aharoni and Eli Berger PDF
Trans. Amer. Math. Soc. 358 (2006), 4895-4917 Request permission

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
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
  • 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.
  • © Copyright 2006 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: Trans. Amer. Math. Soc. 358 (2006), 4895-4917
  • MSC (2000): Primary 05B40
  • DOI: https://doi.org/10.1090/S0002-9947-06-03833-5
  • MathSciNet review: 2231877