(May 2023) Malouf, Brian D.; Sudborough, Ivan Hal; Bereg, Sergey; Chiu, Yun; Raichel, Benjamin; Du, Ding-Zhu; Chandrasekaran, R.

Show more

A permutation array (PA) is a set of permutations on n symbols. A PA is said to have
distance d (under some metric) if every pair of distinct permutations in the array has distance
at least d. Commonly used distance metrics include Hamming distance and Chebyshev
distance. PAs of a known distance can be used to construct error-correcting codes and have
applications in communication over noisy channels.
Let M (n, d) represent the maximum size of a permutation array on n symbols with pairwise
Hamming distance d. Let P (n, d) represent the maximum size of a permutation array
on n symbols with pairwise Chebyshev distance d. Exact values of M (n, d) and P (n, d)
are unknown for most values n and d with the exception of some special cases. While
combinatorial upper and lower bounds exist for both M (n, d) and P (n, d), these can often be
improved through empirical techniques. We present several such techniques to construct PAs
under the Hamming and Chebyshev distance metrics, resulting in improved bounds for both
M (n, d) and P (n, d).