Small arrays of maximum coverage

Given a set S of v ≥ 2 symbols, and integers k ≥ t ≥ 2 and N ≥ 1 , an N × k array A ∈ S N × kis said to cover a t ‐set of columns if all sequences in S t appear as rows in the corresponding N × t subarray of A . If A covers all t ‐subsets of columns, it is called an ( N ; t , k , v ) ‐covering array. These arrays have a wide variety of applications, driving the search for small covering arrays. Here, we consider an inverse problem: rather than aiming to cover all t ‐sets of columns with the smallest possible array, we fix the size N of the array to be equal to v t and try to maximize the number of covered t ‐sets. With the machinery of hypergraph Lagrangians, we provide an upper bound on the number of t ‐sets that can be covered. A linear algebraic construction shows this bound to be tight; exactly so in the case when v is a prime power andv t − 1 v − 1divides k , and asymptotically so in other cases. As an application, by combining our construction with probabilistic arguments, we match the best‐known asymptotics of the covering array number CAN ( t , k , v ) , which is the smallest N for which an ( N ; t , k , v ) ‐covering array exists, and improve the upper bounds on the almost‐covering array number ACAN ( t , k , v , ε ) .