| Abstract: | Given a set S of  symbols, and integers  and  , an  array  is said to cover a t‐set of columns if all sequences in  appear as rows in the corresponding  subarray of A. If A covers all t‐subsets of columns, it is called an  ‐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  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 and  divides 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  , which is the smallest N for which an  ‐covering array exists, and improve the upper bounds on the almost‐covering array number  . |
