|
The intersection of a matroid and a simplicial complex
Author(s):
Ron
Aharoni;
Eli
Berger
Journal:
Trans. Amer. Math. Soc.
358
(2006),
4895-4917.
MSC (2000):
Primary 05B40
Posted:
June 19, 2006
Retrieve article in:
PDF DVI PostScript
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  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  -matroidal colorability of a graph, and prove a fractional version of a conjecture, that every graph  is  -matroidally colorable. The methods used are mostly topological.
References:
-
- 1.
- R. Aharoni, Ryser's conjecture for tri-partite
 -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
 bases in a rank  matroid. Adv. Math. 108(1994), 336-345. MR 1296517 (95h:05040) - 25.
- R. Yuster, Independent transversals in
 -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
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:
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
Posted:
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 of article:
Copyright
2006,
American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.
|
Comments: webmaster@ams.org