# Aharoni-Berger conjecture

**Conjecture**If are matroids on and for every partition of , then there exists with which is independent in every .

Let us begin by stating two classic results. For a graph (or hypergraph) we let denote the size of the smallest (vertex) cover and we let denote the size of the largest matching.

**Theorem (König)**for every bipartite graph.

**Theorem (Matroid Intersection)**If are matroids on and for every partition of , then there exists with which is independent in both and .

The matroid intersection theorem is exactly the case of the above conjecture, but it may also be viewed as a generalization of König's theorem. To see this, let be a bipartite graph with edge set and bipartition and for let be the (uniform) matroid on where a subset is independent if no two edges in share an endpoint in . Then is the number of vertices in which are incident with an edge in , so has minimum value , and a set of edges is independent in both and if and only if it is a matching, so the size of the largest such set is .

A famous conjecture of Ryser suggests a generalization of König's theorem to hypergraphs. It claims that every -partite -uniform hypergraph satisfies . The above conjecture is the common generalization of this conjecture of Ryser and the matroid intersection theorem. Aharoni [A] proved the 3-partite 3-uniform case of Ryser's conjecture, and this was extended by Aharoni-Berger [AB] to the case of the above conjecture. The conjecture remains open for .

## Bibliography

[A] R. Aharoni, Ryser's conjecture for tripartite 3-graphs, Combinatorica 21 (2001), 1-4. MathSciNet

*[AB] R. Aharoni, E. Berger, The intersection of a matroid with a simplicial complex. Trans. Amer. Math. Soc. 358 (2006), no. 11 MathSciNet

* indicates original appearance(s) of problem.