Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-26T19:42:13.339Z Has data issue: false hasContentIssue false
  • English
  • Français

t-Covering Arrays: Upper Bounds and Poisson Approximations

Published online by Cambridge University Press:  12 September 2008

Anant P. Godbole ,
Daphne E. Skipper  and
Rachel A. Sunley
Anant P. Godbole
Affiliation:
Department of Mathematical Sciences, Michigan Technological University, Houghton MI 49931, USA
Daphne E. Skipper
Affiliation:
Department of Mathematics, University of Kentucky, Lexington KY 40506, USA
Rachel A. Sunley
Affiliation:
Department of Mathematics, University of Michigan, Ann Arbor MI 48109, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

A k×n array with entries from the q-letter alphabet {0, 1, …, q − 1} is said to be t-covering if each k × t submatrix has (at least one set of) qt distinct rows. We use the Lovász local lemma to obtain a general upper bound on the minimal number K = K(n, t, q) of rows for which a t-covering array exists; for t = 3 and q = 2, we are able to match the best-known such bound. Let Kλ = Kλ(n, t, q), (λ ≥ 2), denote the minimum number of rows that guarantees the existence of an array for which each set of t columns contains, amongst its rows, each of the qt possible ‘words’ of length t at least λ times. The Lovász lemma yields an upper bound on Kλ that reveals how substantially fewer rows are needed to accomplish subsequent t-coverings (beyond the first). Finally, given a random k × n array, the Stein–Chen method is employed to obtain a Poisson approximation for the number of sets of t columns that are deficient, i.e. missing at least one word.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 5 , Issue 2 , June 1996 , pp. 105 - 117
Copyright
Copyright © Cambridge University Press 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Alon, N. and Spencer, J. (1992) The Probabilistic Method, John Wiley & Sons.Google Scholar
[2]Barbour, A. D., Godbole, A. P. and Qian, J. (1996) Imperfections in random tournaments. Combinatorics, Probability and Computing (to appear).Google Scholar
[3]Barbour, A. D., Holst, L. and Janson, S. (1992) Poisson Approximation, Oxford University Press.CrossRefGoogle Scholar
[4]Bierbrauer, J. (1994) Orthogonal arrays: theory and applications. Preprint.Google Scholar
[5]Bollobás, B. (1978) Extremal Graph Theory, Academic Press.Google Scholar
[6]Godbole, A. P., Skipper, D. E. and Sunley, R. A. (1994) The asymptotic lower bound on the diagonal Ramsey numbers: A closer look, in Discrete Probability and Algorithms, IMA Volumes in Mathematics and its Applications, 72, 81–94, Aldous, D., Diaconis, P., Spencer, J. and Steele, J., eds., Springer- Verlag.Google Scholar
[7]Hedayat, A. S., Sloane, N. J. A. and Stufken, J. (1994) Orthogonal Arrays: Theory and Practice. To appear.Google Scholar
[8]Katona, G. O. H. (1973) Two applications (for search theory and truth functions) of Sperner type theorems. Periodica Mathematica Hungarica 3 19–26.CrossRefGoogle Scholar
[9]Kleitman, D. J. and Spencer, J. (1973) Families of k-independent sets, Discrete Mathematics 6 255–262.CrossRefGoogle Scholar
[10]Rényi, A. (1971) Foundations of Probability, John Wiley & Sons.Google Scholar
[11]Sloane, N. J. A. (1993) Covering arrays and intersecting codes, J. Combinatorial Designs 1 51–63.CrossRefGoogle Scholar
[12]Steele, J. M. (1978) Existence of submatrices with all possible columns, J. Combinatorial Theory A 24 84–88.CrossRefGoogle Scholar