A polynomial construction of perfect sequence covering arrays

Gentle, Aidan R.¹

¹ School of Mathematics Monash University Vic 3800, Australia

Algebraic Combinatorics, Tome 6 (2023) no. 5, pp. 1383-1394

Résumé

A PSCA$(v,t,\lambda )$ is a multiset of permutations of the $v$-element alphabet $\{0,\cdots ,v-1\}$ such that every sequence of $t$ distinct elements of the alphabet appears in the specified order in exactly $\lambda$ permutations. For $v⩾t$, let $g(v,t)$ be the smallest positive integer $\lambda$ such that a PSCA$(v,t,\lambda )$ exists. Kuperberg, Lovett and Peled proved $g(v,t)=O\left(v^t\right)$ using probabilistic methods. We present an explicit construction that proves $g(v,t)=O\left(v^{t(t-2)}\right)$ for fixed $t⩾4$. The method of construction involves taking a permutation representation of the group of projectivities of a suitable projective space of dimension $t-2$ and deleting all but a certain number of symbols from each permutation. In the case that this space is a Desarguesian projective plane, we also show that there exists a permutation representation of the group of projectivities of the plane that covers the vast majority of 4-sequences of its points the same number of times.

Détail

Reçu le : 2022-10-02
Révisé le : 2023-03-27
Accepté le : 2023-03-30
Publié le : 2023-11-07

DOI : 10.5802/alco.308

Classification : 05B30, 05B40, 20B25, 51E20
Keywords: sequence covering array, permutation representation, exact covering, projective geometry

Licence : CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits