Importance: High ✭✭✭
 Author(s): Aharoni, Ron Berger, Eli
 Subject: Combinatorics » Matroid Theory
 Keywords: independent set matroid partition
 Posted by: mdevos on: June 11th, 2007
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.