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$.
Published
2012-01-21
Article Number
P23