Aharoni-Berger conjecture
From Egres Open
(Redirected from The Aharoni-Berger conjecture)
Is it true that if M1,…,Mk are matroids on the same ground set S and k∑i=1ri(Xi)≥(k−1)l for all partitions X1,…,Xk of S, then there exists a common independent set of size l?
Remarks
Ryser's conjecture asks whether for any k-uniform k-partite hypergraph τ≤(k−1)ν holds, where τ is the minimum size of a vertex cover and ν 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