Asymptotically Optimal Covering Designs

A (v,k,t)covering design, orcovering, is a family ofk-subsets, calledblocks, chosen from av-set, such that eacht-subset is contained in at least one of the blocks. The number of blocks is the coveringʹssize, and the minimum size of such a covering is denoted byC(v,k,t). It is easy to see that a covering must contain at least (tv)/(tk) blocks, and in 1985 Rödl [5] proved a long-standing conjecture of Erdos and Hanani [3] that for fixedkandt, coverings of size (tv)/(tk)(1+o(1)) exist (asv→∞). An earlier paper by the first three authors [4] gave new methods for constructing good coverings, and gave tables of upper bounds onC(v,k,t) for smallv,k, andt. The present paper shows that two of those constructions are asymptotically optimal: For fixedkandt, the size of the coverings constructed matches Rödlʹs bound. The paper also makes theo(1) error bound explicit, and gives some evidence for a much stronger bound.