Upper Bounds for Chebyshev Permutation Arrays

We improve on known upper bounds for the size of permutation arrays under the Chebyshev metric, defined as follows. The Chebyshev distance between permutations π and σ on the symbols {1,2,…,n}, denoted by d(π,σ), is max{|πi-σi||1≤i≤n}. For an array <i>A</i> (set) of such permutations, the Chebyshev distance of <i>A</i>, denoted by d(A), is min{d(π,σ)|π,σ∈A,π≠σ}. An array <i>A</i> of such permutations with d(A)=d will be called an (n,d)-PA. Let P(n,d) denote the maximum size of any (n,d)-PA. The function P(n,d) has been the subject of previous research. In this paper, we consider strings on the symbols {0,1,2}, with the 0's representing low symbols and the 2's high symbols for the function P(n,d). An array <i>A</i> of such strings of length <i>n</i> is <i>separable</i> if for any two strings in <i>A</i>, there is a position 1≤i≤n such that the ith symbol in one string is 0 and the ith symbol in the other is a 2. The maximum size of a separable array of strings of length <i>n</i>, with <i>a</i> occurrences of the symbol 0 and <i>b</i> occurrences of the symbol 2, is denoted by R(n;a,b). We show that R(n;k,k) is an upper bound for P(n,n-k) when k≤n2. We derive upper bounds for R(n;a,b) by various recursive and combinatorial methods, from which follow upper bounds for the Chebyshev function P(n,d), which improve upon previous such upper bounds in the literature.