On the structure of small strength-2 covering arrays

A covering array CA(N;t,k,v) of strength t is an Nxk array of symbols from an alphabet of size v such that in every Nxt subarray, every t-tuple occurs in at least one row. A covering array is optimal if it has the smallest possible N for given t, k, and v, and uniform if every symbol occurs [N/v] or [N/v] times in every column. Before 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 Erdos-Ko-Rado Theorem, and 11 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 is 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.