Covering Array Bounds Using Analytical Techniques

A $t$-covering array with entries from the alphabet ${\cal Q}={0,1,\ldots,q-1}$isa$k\times n$stack,sothatforanychoiceof$t$(typicallynon-consecutive)columns,eachofthe$q^{t}$possible$t$-letter words over $\mathcal{Q}$ appear at least once among the rows of the selected columns. We will show how a combination of the Lov'asz local lemma; combinatorial analysis; Stirling’s formula; and Calculus enables one to find better asymptotic bounds for the minimum size of $t$-covering arrays, notably for $t=3,4$. Here size is measured in the number of rows, as expressed in terms of the number of columns.