Published September 2013 | Version public
Journal Article

Covering and packing for pairs

Abstract

When a v-set can be equipped with a set of k-subsets so that every 2-subset of the v-set appears in exactly (or at most, or at least) one of the chosen k-subsets, the result is a balanced incomplete block design (or packing, or covering, respectively). For each k, balanced incomplete block designs are known to exist for all sufficiently large values of v that meet certain divisibility conditions. When these conditions are not met, one can ask for the packing with the most blocks and/or the covering with the fewest blocks. Elementary necessary conditions furnish an upper bound on the number of blocks in a packing and a lower bound on the number of blocks in a covering. In this paper it is shown that for all sufficiently large values of v, a packing and a covering on v elements exist whose numbers of blocks differ from the basic bounds by no more than an additive constant depending only on k.

Additional Information

© 2013 Elsevier Inc. Received 24 September 2011. Available online 23 April 2013. We thank an anonymous referee for helpful comments on the presentation.

Additional details

Identifiers

Eprint ID
41568
Resolver ID
CaltechAUTHORS:20130930-153617380

Dates

Created
2013-09-30
Created from EPrint's datestamp field
Updated
2021-11-10
Created from EPrint's last_modified field