Noga Alon, Béla Bollobás, Jeong Han Kim and Van H. Vu

A cover of a hypergraph is a collection of edges whose union contains all vertices. Let $H = (V, E)$ be a $k$-uniform, $D$-regular hypergraph on $n$ vertices, in which no two vertices are contained in more than $o(D / e^{2k} \log D)$ edges as $D$ tends to infinity. Our results include the fact that if $k = o(\log D)$, then there is a cover of $(1 + o(1)) n / k$ edges, extending the known result that this holds for fixed $k$. On the other hand, if $k \geq 4 \log D $ then there are $k$-uniform, $D$-regular hypergraphs on $n$ vertices in which no two vertices are contained in more than one edge, and yet the smallest cover has at least $\Omega (\frac {n}{k} \log (\frac {k}{\log D} ))$ edges. Several extensions and variants are also obtained, as well as the following geometric application. The minimum number of lines required to separate $n$ random points in the unit square is, almost surely, $\Theta (n^{2/3} / (\log n)^{1/3}).$

2000 Mathematical Subject Classification: 05C65, 05D15, 60D05.

Keywords: hypergraph covering, hypergraph matching, random point sets.

E-mail: noga@math.tau.ac.il, bollobas@mathsci.msci.memphis.edu, jehkim@microsoft.com, vanvu@ucsd.edu