Remote Access Transactions of the American Mathematical Society
Green Open Access

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

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?)

  • 1. R. Aharoni, Ryser's conjecture for tri-partite $ 3$-graphs, Combinatorica, 21(2001), 1-4. MR 1805710 (2002c:05157)
  • 2. R. Aharoni, E. Berger and R. Ziv, A tree version of König's theorem, Combinatorica, 22(2002), 335-343. MR 1932057 (2003j:05098)
  • 3. R. Aharoni, E. Berger and R. Ziv, Independent systems of representatives in weighted graphs, to appear in Combinatorica.
  • 4. R. Aharoni, M. Chudnovsky and A. Kotlov, Triangulated spheres and colored cliques, Disc. Comp. Geometry 28(2002), 223-229. MR 1920141 (2003g:52029)
  • 5. R. Aharoni and R. Ziv, The intersection of two infinite matroids, J. London Math. Soc. 58(1998), 513-525. MR 1678148 (99m:05042)
  • 6. R. Aharoni and P. Haxell, Hall's theorem for hypergraphs, J. of Graph Theory 35(2000), 83-88. MR 1781189 (2001h:05072)
  • 7. A. Björner, B. Korte and L. Lovász, Homotopy properties of greedoids, Adv. in Appl. Math. 6, 447-494. MR 0826593 (87d:05051)
  • 8. J. Davies and C. McDiarmid, Disjoint common transversals and exchange structures, J. London Math. Soc. 14(1976), 55-62. MR 0429574 (55:2586)
  • 9. M. DeVos, Stable bases and circuit decompositions, preprint.
  • 10. J. Edmonds, Lehman's switching game and a theorem of Tutte and Nash-Williams, J. Res. Nat. Bur. Stand. 69B(1965), 73-77. MR 0190026 (32:7442)
  • 11. J. Edmonds, Matroid intersection, Discrete optimization Ann. Discrete Math. 4(1979), 39-49. MR 0558553
  • 12. H. Fleischner and M. Stiebitz, A solution to a colouring problem of P. Erdos, Discrete Math. 101(1992), 39-48. MR 1172363 (93g:05050)
  • 13. A. Frank, A weighted matroid intersection algorithm, J. Algorithms 2(1981), 328-336. MR 0640517 (83f:68024)
  • 14. B. Knaster, C. Kuratowski, and C. Mazurkiewicz, Ein Beweis des Fixpunktsatzes fuer n-dimensionale Simplexe, Fundamenta Mathematicae 14 (1929), 132-137.
  • 15. D. König, Über Graphen und ihre Andwendung auf Determinantentheorie und Mengenlehre, Math Ann. 77 (1916), Jbuch. 46.146-147.
  • 16. P. Hall, On representation of subsets, J. London Math. Soc. 10(1935), 26-30.
  • 17. P. E. Haxell, A condition for matchability in hypergraphs, Graphs and Combinatorics 11 (1995), 245-248. MR 1354745 (96g:05104)
  • 18. P. E. Haxell, On the strong chromatic number, Comb. Prob. and Computing 13(2004), 857-865. MR 2102412 (2005g:05055)
  • 19. R. Meshulam, The clique complex and hypergraph matching, Combinatorica 21(2001) 89-94. MR 1805715 (2001m:05089)
  • 20. R. Meshulam, Domination numbers and homology, Jour. Combin. Th., Ser. A, 102(2003), 321-330. MR 1979537 (2004c:05144)
  • 21. A. Schrijver, Combinatorial Optimization, Vol. A-C, Springer-Verlag, 2003. MR 1956924 (2004b:90004a); MR 1956925 (2004b:90004b); MR 1956926 (2004b:90004c)
  • 22. D. J. A. Welsh, Matroid Theory, Academic Press, 1976. MR 0427112 (55:148)
  • 23. D. J. A. Welsh, On matroid theorems of Edmonds and Rado, J. London Math. Soc. 2(1970), 251-256. MR 0258663 (41:3309)
  • 24. M. Wild, On Rota's problem about $ n$ bases in a rank $ n$ matroid. Adv. Math. 108(1994), 336-345. MR 1296517 (95h:05040)
  • 25. R. Yuster, Independent transversals in $ r$-partite graphs, Discrete Math. 176(1997), 255-261. MR 1477294 (98f:05092)

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

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

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.

American Mathematical Society