On the structure of small strength‐2 covering arrays. Issue 1 (8th September 2019)

• Record Type: Journal Article
• Authors: Kokkala, Janne I.; Meagher, Karen; Naserasr, Reza; Nurmela, Kari J.; Östergård, Patric R. J.; Stevens, Brett
• Is Part Of: Journal of combinatorial designs. Volume 28:Issue 1(2020:Jan.)
• Page Start: 5
• Page End: 24
• Publication Date: 2019-09-08
• Subjects: bounds -- computational enumeration -- covering array; Combinatorial designs and configurations -- Periodicals; Configurations et schémas combinatoires -- Périodiques; 511.6
• DOI: 10.1002/jcd.21671
• Languages: English
• ISSNs: 1063-8539

Abstract

Abstract: A covering array CA ( N ; t, k, v ) of strength t is an N × k array of symbols from an alphabet of size v such that in every N × t 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 Erdős‐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.