Multiple contractions of permutation arrays

Abstract

Given a permutation $\sigma$ on $n$ symbols $\{0,1,\dots ,n-1\}$ and an integer $1\le m\le n-1$, the $m$th contraction of $\sigma$ is the permutation ${\sigma }^{{\mathsf{CT}}^m}$ on $n-m$ symbols obtained by deleting the symbols $n-1,n-2,\dots ,n-m$ from the cycle decomposition of $\sigma$. The Hamming distance $\mathrm{hd}(\sigma ,\tau )$ between two permutations $\sigma$ and $\tau$ is the number of symbols $x$ such that $\sigma (x)\ne \tau (x)$. In this paper we give a complete characterization of the effect of a single contraction on the Hamming distance between two permutations. This allows us to obtain sufficient conditions for $\mathrm{hd}(\sigma ,\tau )-\mathrm{hd}({\sigma }^{{\mathsf{CT}}^m},{\tau }^{{\mathsf{CT}}^m})\le 2m$.

arXiv comment15 pages, 6 tables