TY - JOUR
T1 - Asymptotically good coverings
AU - Spencer, Joel
PY - 1985/6
Y1 - 1985/6
N2 - The Erdos-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.
AB - The Erdos-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.
UR - http://www.scopus.com/inward/record.url?scp=84972584069&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84972584069&partnerID=8YFLogxK
U2 - 10.2140/pjm.1985.118.575
DO - 10.2140/pjm.1985.118.575
M3 - Article
AN - SCOPUS:84972584069
SN - 0030-8730
VL - 118
SP - 575
EP - 586
JO - Pacific Journal of Mathematics
JF - Pacific Journal of Mathematics
IS - 2
ER -