On Ryser's conjecture

P. E. Haxell, A. D. Scott

Abstract


Motivated by an old problem known as Ryser's Conjecture, we prove that for $r=4$ and $r=5$, there exists $\epsilon>0$ such that every $r$-partite $r$-uniform hypergraph $\cal H$ has a cover of size at most $(r-\epsilon)\nu(\cal H)$, where $\nu(\cal H)$ denotes the size of a largest matching in $\cal H$.

Full Text: PDF