Excess coverage arrays and Levenshtein’s conjecture

Abstract A sequence covering array, denoted by ( N ; t , v ), is a set of N permutations of $$\{0, \dots , v-1 \}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>{</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>,</mml:mo> <mml:mi>v</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> such that each sequence of t distinct elements of $$\{0, \dots , v-1\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>{</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>,</mml:mo> <mml:mi>v</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> 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 &gt; 4$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>4</mml:mn> </mml:mrow> </mml:math> , if a sequence covering array with t ! permutations exists, then $$v \in \{t,t+1\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>v</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>{</mml:mo> <mml:mi>t</mml:mi> <mml:mo>,</mml:mo> <mml:mi>t</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> . 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.