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.
- Ron Aharoni, Ryser’s conjecture for tripartite 3-graphs, Combinatorica 21 (2001), no. 1, 1–4. MR 1805710, DOI 10.1007/s004930170001
- Ron Aharoni, Eli Berger, and Ran Ziv, A tree version of Kőnig’s theorem, Combinatorica 22 (2002), no. 3, 335–343. MR 1932057, DOI 10.1007/s004930200016
- R. Aharoni, E. Berger and R. Ziv, Independent systems of representatives in weighted graphs, to appear in Combinatorica.
- Ron Aharoni, Maria Chudnovsky, and Andreĭ Kotlov, Triangulated spheres and colored cliques, Discrete Comput. Geom. 28 (2002), no. 2, 223–229. MR 1920141, DOI 10.1007/s00454-002-2792-6
- Ron Aharoni and Ran Ziv, The intersection of two infinite matroids, J. London Math. Soc. (2) 58 (1998), no. 3, 513–525. MR 1678148, DOI 10.1112/S0024610798006723
- Ron Aharoni and Penny Haxell, Hall’s theorem for hypergraphs, J. Graph Theory 35 (2000), no. 2, 83–88. MR 1781189, DOI 10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V
- Anders Björner, Bernhard Korte, and László Lovász, Homotopy properties of greedoids, Adv. in Appl. Math. 6 (1985), no. 4, 447–494. MR 826593, DOI 10.1016/0196-8858(85)90021-1
- Joan Davies and Colin McDiarmid, Disjoint common transversals and exchange structures, J. London Math. Soc. (2) 14 (1976), no. 1, 55–62. MR 429574, DOI 10.1112/jlms/s2-14.1.55
- M. DeVos, Stable bases and circuit decompositions, preprint.
- Jack Edmonds, Lehman’s switching game and a theorem of Tutte and Nash-Williams, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 73–77. MR 190026, DOI 10.6028/jres.069B.005
- Jack Edmonds, Matroid intersection, Ann. Discrete Math. 4 (1979), 39–49. Discrete optimization (Proc. Adv. Res. Inst. Discrete Optimization and Systems Appl., Banff, Alta., 1977), I. MR 558553, DOI 10.1016/S0167-5060(08)70817-3
- Herbert Fleischner and Michael Stiebitz, A solution to a colouring problem of P. Erdős, Discrete Math. 101 (1992), no. 1-3, 39–48. Special volume to mark the centennial of Julius Petersen’s “Die Theorie der regulären Graphs”, Part II. MR 1172363, DOI 10.1016/0012-365X(92)90588-7
- András Frank, A weighted matroid intersection algorithm, J. Algorithms 2 (1981), no. 4, 328–336. MR 640517, DOI 10.1016/0196-6774(81)90032-8
- B. Knaster, C. Kuratowski, and C. Mazurkiewicz, Ein Beweis des Fixpunktsatzes fuer n-dimensionale Simplexe, Fundamenta Mathematicae 14 (1929), 132-137.
- D. König, Über Graphen und ihre Andwendung auf Determinantentheorie und Mengenlehre, Math Ann. 77 (1916), Jbuch. 46.146-147.
- P. Hall, On representation of subsets, J. London Math. Soc. 10(1935), 26-30.
- P. E. Haxell, A condition for matchability in hypergraphs, Graphs Combin. 11 (1995), no. 3, 245–248. MR 1354745, DOI 10.1007/BF01793010
- P. E. Haxell, On the strong chromatic number, Combin. Probab. Comput. 13 (2004), no. 6, 857–865. MR 2102412, DOI 10.1017/S0963548304006157
- Roy Meshulam, The clique complex and hypergraph matching, Combinatorica 21 (2001), no. 1, 89–94. MR 1805715, DOI 10.1007/s004930170006
- Roy Meshulam, Domination numbers and homology, J. Combin. Theory Ser. A 102 (2003), no. 2, 321–330. MR 1979537, DOI 10.1016/S0097-3165(03)00045-1
- Alexander Schrijver, Combinatorial optimization. Polyhedra and efficiency. Vol. A, Algorithms and Combinatorics, vol. 24, Springer-Verlag, Berlin, 2003. Paths, flows, matchings; Chapters 1–38. MR 1956924
- D. J. A. Welsh, Matroid theory, L. M. S. Monographs, No. 8, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. MR 0427112
- D. J. A. Welsh, On matroid theorems of Edmonds and Rado, J. London Math. Soc. (2) 2 (1970), 251–256. MR 258663, DOI 10.1112/jlms/s2-2.2.251
- Marcel Wild, On Rota’s problem about $n$ bases in a rank $n$ matroid, Adv. Math. 108 (1994), no. 2, 336–345. MR 1296517, DOI 10.1006/aima.1994.1073
- Raphael Yuster, Independent transversals in $r$-partite graphs, Discrete Math. 176 (1997), no. 1-3, 255–261. MR 1477294, DOI 10.1016/S0012-365X(96)00300-7
- Ron Aharoni
- Affiliation: Department of Mathematics, Technion, Israel Institute of Technology, Haifa, Israel 32000
- Email: email@example.com
- 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