# Aharoni-Berger conjecture

Jump to: navigation, search

Is it true that if $M_1, \ldots, M_k$ are matroids on the same ground set S and $\sum_{i=1}^k r_i (X_i) \geq (k-1)l$ for all partitions $X_1, \ldots, X_k$ 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 $\tau \leq (k-1)\nu$ holds, where $\tau$ is the minimum size of a vertex cover and $\nu$ 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

1. R. Aharoni, Ryser's conjecture for tripartite 3-graphs, Combinatorica 21 (2001), 1-4. DOI link
2. 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