On asymmetric coverings and covering numbers

✍ Scribed by David Applegate; E. M. Rains; N. J. A. Sloane

• Book ID: 102307100
• Publisher: John Wiley and Sons
• Year: 2003
• Tongue: English
• Weight: 111 KB
• Volume: 11
• Category: Article
• ISSN: 1063-8539
• DOI: 10.1002/jcd.10022

✦ Synopsis

Abstract

An asymmetric covering ${\cal D}(n,R)$ is a collection of special subsets S of an n‐set such that every subset T of the n‐set is contained in at least one special S with $|S| - |T| \le R$. In this paper we compute the smallest size of any ${\cal D}(n,1)$ for $n \le 8.$ We also investigate “continuous” and “banded” versions of the problem. The latter involves the classical covering numbers $C(n,k,k-1)$, and we determine the following new values: $C(10,5,4) = 51$, $C(11,7,6) =84 $, $C(12,8,7) = 126 $, $C(13,9,8)= 185$, and $C(14,10,9) = 259$. We also find the number of non‐isomorphic minimal covering designs in several cases. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 218–228, 2003; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/jcd.10022