Codes and Expansions (CodEx) Seminar

Jonathan Jedwab (Simon Fraser University)
Perfect sequence covering arrays

An \((n,k,\lambda)\) perfect sequence covering array is a multiset whose elements are permutations of the sequence \((1, 2, \dots, n)\) and which collectively contain each ordered \(k\)-subsequence exactly \(\lambda\) times. The central question is: for given \(n\) and \(k\), what is the smallest value of \(\lambda\) (denoted \(g(n,k)\)) for which such a configuration exists? We interpret the sequences of a perfect sequence covering array as elements of the symmetric group \(S_n\), and constrain its structure to be a union of cosets of a prescribed subgroup of \(S_n\). By adapting a search algorithm due to Mathon and van Trung for finding spreads, we obtain highly structured examples of perfect sequence covering arrays. In particular, we determine that \(g(6,3) = g(7,3) = g(7,4) = 2\) and \(g(7,5) \in \{2,3,4\}\) and \(g(8,3) \in \{2,3\}\) and \(g(9,3) \in \{2,3,4\}\).

This is joint work with Jingzhou Na and Shuxing Li.