CaltechAUTHORS
  A Caltech Library Service

Covering and packing for pairs

Chee, Yeow Meng and Colbourn, Charles J. and Ling, Alan C. H. and Wilson, Richard M. (2013) Covering and packing for pairs. Journal of Combinatorial Theory. Series A, 120 (7). pp. 1440-1449. ISSN 0097-3165. doi:10.1016/j.jcta.2013.04.005. https://resolver.caltech.edu/CaltechAUTHORS:20130930-153617380

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20130930-153617380

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1016/j.jcta.2013.04.005 DOIArticle
http://www.sciencedirect.com/science/article/pii/S0097316513000691PublisherArticle
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.
Subject Keywords: Balanced incomplete block design; Pair packing; Pair covering; Group divisible design; Pairwise balanced design
Issue or Number:7
DOI:10.1016/j.jcta.2013.04.005
Record Number:CaltechAUTHORS:20130930-153617380
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20130930-153617380
Official Citation:Yeow Meng Chee, Charles J. Colbourn, Alan C.H. Ling, Richard M. Wilson, Covering and packing for pairs, Journal of Combinatorial Theory, Series A, Volume 120, Issue 7, September 2013, Pages 1440-1449, ISSN 0097-3165, http://dx.doi.org/10.1016/j.jcta.2013.04.005. (http://www.sciencedirect.com/science/article/pii/S0097316513000691)
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:41568
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:30 Sep 2013 22:52
Last Modified:10 Nov 2021 04:31

Repository Staff Only: item control page