Asymptotically good coverings

Joel Spencer

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)575-586
Number of pages12
JournalPacific Journal of Mathematics
Volume118
Issue number2
DOIs
StatePublished - Jun 1985

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Asymptotically good coverings'. Together they form a unique fingerprint.

Cite this