Asymptotically good coverings

Joel Spencer

Vol. 118 (1985), No. 2, 575–586

DOI: 10.2140/pjm.1985.118.575

Abstract

The Erdős-Hanani conjecture is that for fixed r < k and n large there exists a covering of all r-sets of an n-set by a family of k-sets whose cardinality is asymptotic (in n) to the “counting” lower bound. This conjecture was first proven by Rodl, here we give a more direct argument. We use probabilistic methods, selecting k-sets in large groups, and showing that the hypergraph of uncovered r-sets retains a property we call quasirandomness, meaning that it has the essential (for us) properties of random hypergraph.

Mathematical Subject Classification 2000

Primary: 05B40

Secondary: 05C80

Milestones

Received: 31 May 1984

Published: 1 June 1985