Aharoni-Berger conjecture
Is it true that if [math]M_1, \ldots, M_k[/math] are matroids on the same ground set S and [math]\sum_{i=1}^k r_i (X_i) \geq (k-1)l[/math] for all partitions [math]X_1, \ldots, X_k[/math] of S, then there exists a common independent set of size [math]l[/math]?
Remarks
Ryser's conjecture asks whether for any k-uniform k-partite hypergraph [math]\tau \leq (k-1)\nu[/math] holds, where [math]\tau[/math] is the minimum size of a vertex cover and [math]\nu[/math] is the maximum number of disjoint hyperedges. The case k=2 is just Kőnig's theorem, while the case k=3 was proved by Aharoni [1]. Just as Edmonds' matroid intersection theorem generalizes Kőnig's theorem, the Ryser conjecture is generalized by the Aharoni-Berger conjecture. It was proved for k=3 by Aharoni and Berger [2].
References
- ↑ R. Aharoni, Ryser's conjecture for tripartite 3-graphs, Combinatorica 21 (2001), 1-4. DOI link
- ↑ R. Aharoni, E. Berger, The intersection of a matroid with a simplicial complex, Trans. Amer. Math. Soc. 358 (2006), 4895-4917. DOI link, JSTOR link
