ALGEBRAIC COMBINATORICS

no. 5
A polynomial construction of perfect sequence covering arrays
Gentle, Aidan R.1
1 School of Mathematics Monash University Vic 3800, Australia
Algebraic Combinatorics, Volume 6 (2023) no. 5, pp. 1383-1394.

A PSCA(v,t,λ) is a multiset of permutations of the v-element alphabet {0,⋯,v-1} such that every sequence of t distinct elements of the alphabet appears in the specified order in exactly λ permutations. For v⩾t, let g(v,t) be the smallest positive integer λ such that a PSCA(v,t,λ) exists. Kuperberg, Lovett and Peled proved g(v,t)=O(v t ) using probabilistic methods. We present an explicit construction that proves g(v,t)=O(v t(t-2) ) 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.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.308
Classification: 05B30, 05B40, 20B25, 51E20
Keywords: sequence covering array, permutation representation, exact covering, projective geometry
Gentle, Aidan R. 1

1 School of Mathematics Monash University Vic 3800, Australia
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2023__6_5_1383_0,
     author = {Gentle, Aidan R.},
     title = {A polynomial construction of perfect sequence covering arrays},
     journal = {Algebraic Combinatorics},
     pages = {1383--1394},
     publisher = {The Combinatorics Consortium},
     volume = {6},
     number = {5},
     year = {2023},
     doi = {10.5802/alco.308},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.308/}
}
TY  - JOUR
AU  - Gentle, Aidan R.
TI  - A polynomial construction of perfect sequence covering arrays
JO  - Algebraic Combinatorics
PY  - 2023
SP  - 1383
EP  - 1394
VL  - 6
IS  - 5
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.308/
DO  - 10.5802/alco.308
LA  - en
ID  - ALCO_2023__6_5_1383_0
ER  - 
%0 Journal Article
%A Gentle, Aidan R.
%T A polynomial construction of perfect sequence covering arrays
%J Algebraic Combinatorics
%D 2023
%P 1383-1394
%V 6
%N 5
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.308/
%R 10.5802/alco.308
%G en
%F ALCO_2023__6_5_1383_0
Gentle, Aidan R. A polynomial construction of perfect sequence covering arrays. Algebraic Combinatorics, Volume 6 (2023) no. 5, pp. 1383-1394. doi : 10.5802/alco.308. https://alco.centre-mersenne.org/articles/10.5802/alco.308/

[1] Ball, Simeon; Lavrauw, Michel Arcs in finite projective spaces, EMS Surv. Math. Sci., Volume 6 (2019) no. 1-2, pp. 133-172 | DOI | MR | Zbl

[2] Chee, Yeow Meng; Colbourn, Charles J.; Horsley, Daniel; Zhou, Junling Sequence covering arrays, SIAM J. Discrete Math., Volume 27 (2013) no. 4, pp. 1844-1861 | DOI | MR | Zbl

[3] Dushnik, Ben Concerning a certain set of arrangements, Proc. Amer. Math. Soc., Volume 1 (1950), pp. 788-796 | DOI | MR | Zbl

[4] Gentle, Aidan R.; Wanless, Ian M. On perfect sequence covering arrays, Ann. Comb., Volume 27 (2023), pp. 539-564 | DOI | MR

[5] Hirschfeld, J. W. P. Projective geometries over finite fields, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1979, xii+474 pages | MR

[6] Itoh, Toshiya; Takei, Yoshinori; Tarui, Jun On permutations with limited independence, Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 2000), ACM, New York (2000), pp. 137-146 | MR | Zbl

[7] Iurlano, Enrico Growth of the perfect sequence covering array number, Des. Codes Cryptogr., Volume 91 (2023) no. 4, pp. 1487-1494 | DOI | MR | Zbl

[8] Klein, Andreas On perfect deletion-correcting codes, J. Combin. Des., Volume 12 (2004) no. 1, pp. 72-77 | DOI | MR | Zbl

[9] Kuhn, D. Richard; Higdon, James M.; Lawrence, James F.; Kacker, Raghu N.; Lei, Yu Combinatorial methods for event sequence testing, 2012 IEEE Fifth International Conference on Software Testing, Verification and Validation, IEEE (2012), pp. 601-609 | DOI

[10] Kuperberg, Greg; Lovett, Shachar; Peled, Ron Probabilistic existence of regular combinatorial structures, Geom. Funct. Anal., Volume 27 (2017) no. 4, pp. 919-972 | DOI | MR | Zbl

[11] Levenshteĭn, V. I. Perfect codes in the metric of deletions and insertions, Diskret. Mat., Volume 3 (1991) no. 1, pp. 3-20 | DOI | MR | Zbl

[12] Mathon, Rudolf; Tran, Van Trung Directed t-packings and directed t-Steiner systems, Volume 18, 1999 no. 1-3, pp. 187-198 (Designs and codes—a memorial tribute to Ed Assmus) | DOI | MR | Zbl

[13] Na, Jingzhou; Jedwab, Jonathan; Li, Shuxing A group-based structure for perfect sequence covering arrays, Des. Codes Cryptogr., Volume 91 (2023) no. 3, pp. 951-970 | DOI | MR | Zbl

[14] Singer, James A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc., Volume 43 (1938) no. 3, pp. 377-385 | DOI | MR | Zbl

[15] Spencer, J. Minimal scrambling sets of simple orders, Acta Math. Acad. Sci. Hungar., Volume 22 (1971/72), pp. 349-353 | DOI | MR | Zbl

[16] Thas, J. A. Some results concerning {(q+1)(n-1);n}-arcs and {(q+1) (n-1)+1;n}-arcs in finite projective planes of order q, J. Combinatorial Theory Ser. A, Volume 19 (1975) no. 2, pp. 228-232 | DOI | MR | Zbl

[17] Yuster, Raphael Perfect sequence covering arrays, Des. Codes Cryptogr., Volume 88 (2020) no. 3, pp. 585-593 | DOI | MR | Zbl

Cited by Sources: