Publication Date:
2003-03-01
Description:
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.
Print ISSN:
0024-6115
Electronic ISSN:
1460-244X
Topics:
Mathematics
Permalink