Random Covering Designs

✍ Scribed by Anant P. Godbole; Svante Janson

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 559 KB
• Volume: 75
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.1996.0065

✦ Synopsis

A t&(n, k, *) covering design (n k>t 2) consists of a collection of k-element subsets (blocks) of an n-element set X such that each t-element subset of X occurs in at least * blocks. Let *=1 and k 2t&1. Consider a randomly selected collection B of blocks; |B| =,(n). We use the correlation inequalities of Janson to show that B exhibits a rather sharp threshold behaviour, in the sense that the probability that it constitutes a t&(n, k, 1) covering design is, asymptotically, zero or one according as

is arbitrary. We then use the Stein Chen method of Poisson approximation to show that the restrictive condition k 2t&1 in the above result can be dispensed with. More generaly, we prove that if each block is independently ``selected'' with a certain probability p, the distribution of the number W of uncovered t sets can be approximated by that of a Poisson random variable provided that E |B| [( n t )Â( k t )][(t&1) log n+log log n+a n ], where a n Ä at an arbitrarily slow rate.