The intersection of a matroid and a simplicial complex

Aharoni, Ron; Berger, Eli

doi:10.1090/S0002-9947-06-03833-5

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

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