2022/11/02 by Calbert, Mason R., Dougherty, Ryan E.
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2211.01209
A covering array is an N × k array of elements from a v-ary alphabet such that every N × t subarray contains all vt tuples from the alphabet of size t at least λ times; this is denoted as \CAλ(N; t, k, v). Covering arrays have applications in the testing of large-scale complex systems; in systems that are nondeterministic, increasing λ gives greater confidence in the system's correctness. The covering array number, \CANλ(t,k,v) is the smallest number of rows for which a covering array on the other parameters exists. For general λ, only several nontrivial bounds are known, the smallest of which was asymptotically log k + λlog log k + o(λ) when v, t are fixed. Additionally it has been conjectured that the log log k term can be removed. First, we affirm the conjecture by deriving an asymptotically optimal bound for \CANλ(t,k,v) for general λ and when v, t are constant using the Stein--Lovász--Johnson paradigm. Second, we improve upon the constants of this method using the Lovász local lemma. Third, when λ=2, we extend a two-stage paradigm of Sarkar and Colbourn that improves on the general bound and often produces better bounds than even when λ=1 of other results. Fourth, we extend this two-stage paradigm further for general λ to obtain an even stronger upper bound, including using graph coloring. And finally, we determine a bound on how large λ can be for when the number of rows is fixed.