Upper Bounds for Covering Arrays of Higher Index

arXiv2211.01209MaRDI QIDQ6415944FDOQ6415944

Authors: Mason R. Calbert, Ryan E. Dougherty 

Publication date: 2 November 2022

Abstract: A emph{covering array} is an $Nimesk$ array of elements from a $v$-ary alphabet such that every $Nimest$ subarray contains all $v^t$ tuples from the alphabet of size $t$ at least $lambda$ times; this is denoted as $C{A}_{l}ambda(N;t,k,v)$. Covering arrays have applications in the testing of large-scale complex systems; in systems that are nondeterministic, increasing $lambda$ gives greater confidence in the system's correctness. The emph{covering array number}, $CA{N}_{l}ambda(t,k,v)$ is the smallest number of rows for which a covering array on the other parameters exists. For general $lambda$, only several nontrivial bounds are known, the smallest of which was asymptotically $logk+lambdaloglogk+o(lambda)$ when $v,t$ are fixed. Additionally it has been conjectured that the $loglogk$ term can be removed. First, we affirm the conjecture by deriving an asymptotically optimal bound for $CA{N}_{l}ambda(t,k,v)$ for general $lambda$ and when $v,t$ are constant using the Stein--Lov'asz--Johnson paradigm. Second, we improve upon the constants of this method using the Lov'asz local lemma. Third, when $lambda=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 $lambda=1$ of other results. Fourth, we extend this two-stage paradigm further for general $lambda$ to obtain an even stronger upper bound, including using graph coloring. And finally, we determine a bound on how large $lambda$ can be for when the number of rows is fixed.

This page was built for publication: Upper Bounds for Covering Arrays of Higher Index

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6415944)