Economical covers with geometric applications

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

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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/e2klog 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 ≥ 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 ω((n/k) log (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, θ(n2/3/(log n)1/3).

Original languageEnglish (US)
Pages (from-to)273-301
Number of pages29
JournalProceedings of the London Mathematical Society
Volume86
Issue number2
DOIs
StatePublished - Mar 2003
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Economical covers with geometric applications'. Together they form a unique fingerprint.

Cite this