Answers are grounded in this paper and cite their sources.
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) q t 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 q t 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.
No takes yet. Share an insight, caveat, or question.
Godbole et al. (1996) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: