Upper bounds on the sizes of variable strength covering arrays using the Lovász local lemma (Q2333832): Difference between revisions

The probabilistic method (see [\textit{N. Alon} and \textit{J. H. Spencer}, The probabilistic method. 4th edition. Hoboken, NJ: John Wiley \& Sons (2016; Zbl 1333.05001)]) has been used extensively in Graph Theory, Combinatorics and other areas in the past few decades. One of the most powerful tools developed in the realm of the probabilistic method is the Lovász local lemma and its variants. \textit{C. J. Colbourn} et al. [Des. Codes Cryptography 86, No. 4, 907--937 (2018; Zbl 1383.05045)] used the probabilistic method previously, to establish asymptotic upper bounds for the so-called \(\mathrm{CAN} (t, k, v)\), the covering array number, that is logarithmic on the number of columns of the array. In this paper, the authors establish an explicit upper bound on \(\mathrm{VCAN} (H, v)\), the so-called variable-strength covering array number. Determining the smallest number of rows for which specific covering arrays exist, called CAN, is a very challenging task. With current methods, this is only possible for a very small subset of covering arrays, for all other instances we need to rely on methods that can provide tight upper bounds on CAN. In this work, not only do the authors adapt an existing probabilistic approach to obtain upper bounds on CAN-based on the Lovász local lemma to covering arrays of variable strength, which can be considered a generalization of covering arrays, but also provide a comparison between upper bounds derived by the symmetrical, asymmetrical as well as general Lovász local lemma.