On the Structure of Small Strength-$2$ Covering Arrays

Abstract

A covering array $\mathrm{CA}(\mathrm{N};\mathrm{t},\mathrm{k},\mathrm{v})$ of strength $t$ is an $N\times k$ array of symbols from an alphabet of size $v$ such that in every $N\times t$ subarray, every $t$-tuple occurs in at least one row. A covering array is \emph{optimal} if it has the smallest possible $N$ for given $t$, $k$, and $v$, and \emph{uniform} if every symbol occurs $\lfloor N/v\rfloor$ or $\lceil N/v\rceil$ times in every column. Prior to this paper the only known optimal covering arrays for $t=2$ were orthogonal arrays, covering arrays with $v=2$ constructed from Sperner's Theorem and the Erdős-Ko-Rado Theorem, and eleven other parameter sets with $v>2$ and $N>v^2$. In all these cases, there is a uniform covering array with the optimal size. It has been conjectured that there exists a uniform covering array of optimal size for all parameters. In this paper a new lower bound as well as structural constraints for small uniform strength-$2$ covering arrays are given. Moreover, covering arrays with small parameters are studied computationally. The size of an optimal strength-$2$ covering array with $v>2$ and $N>v^2$ is now known for $21$ parameter sets. Our constructive results continue to support the conjecture.