Title: Perfect Sequence Covering Arrays: An Overview

Abstract: Consider a set P of permutations of [n] = 1, 2, . . . , n, viewed as a set of ordered n-tuples. Assume that every ordered k-subsequence of distinct elements from [n] appears the same number of times across the permutations in P. What is the minimum possible size of P? This natural question connects to directed t-designs, perfect deletion-correction codes, k-rankwise independent families of permutations, and a recent resurgence motivated by the introduction of perfect sequence covering arrays by Raphael Yuster. This talk surveys progress on this problem from several perspectives, with an emphasis on a common group-based structure present in certain perfect sequence covering arrays identified via sophisticated computer search.

Part of this talk is based on joint work with Jonathan Jedwab and Jingzhou Na (Simon Fraser University).