Extremal hypergraphs for Ryser's Conjecture

摘要

Ryser's Conjecture states that any r-partite r-uniform hypergraph has a vertex cover of size at most r - 1 times the size of the largest matching. For r = 2, the conjecture is simply Konig's Theorem and every bipartite graph is a witness for its tightness. The conjecture has also been proven for r = 3 by Aharoni using topological methods, but the proof does not give information on the extremal 3-uniform hypergraphs. Our goal in this paper is to characterize those hypergraphs which are tight for Aharoni's Theorem.