Designs, Codes and Cryptography Computer Science Applications

Excess coverage arrays and Levenshtein’s conjecture

Amber E. Gentle, Daniel Horsley, Ian M. Wanless
Springer Nature · 2025-08-30 · DOI 10.1007/s10623-025-01722-9

Abstract

Abstract A sequence covering array, denoted by ( N ; t , v ), is a set of N permutations of $$\{0, \dots , v-1 \}$$ { 0 , ⋯ , v - 1 } such that each sequence of t distinct elements of $$\{0, \dots , v-1\}$$ { 0 , ⋯ , v - 1 } is a (not necessarily contiguous) subsequence of at least one permutation. The minimum number of permutations such a sequence covering array can have is t ! and it has been conjectured that for $$t > 4$$ t > 4 , if a sequence covering array with t ! permutations exists, then $$v \in \{t,t+1\}$$ v ∈ { t , t + 1 } . In this paper, we prove that an (7!; 7, 10) does not exist. We do this by analysing connections between sequence covering arrays and a special kind of covering array called an excess coverage array.

Read at publisher →