Premium
Small arrays of maximum coverage
Author(s) -
Das Shagnik,
Mészáros Tamás
Publication year - 2018
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21609
Subject(s) - hypergraph , cover (algebra) , mathematics , row , combinatorics , upper and lower bounds , algebraic number , set (abstract data type) , row and column spaces , inverse , discrete mathematics , probabilistic logic , computer science , geometry , mechanical engineering , mathematical analysis , statistics , database , engineering , programming language
Abstract 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 , ε ) .