Upper Bounds for Chebyshev Permutation Arrays.

Area of Science:

• Combinatorics
• Discrete Mathematics
• Information Theory

Background:

• Permutation arrays are sets of permutations with specific distance properties.
• The Chebyshev metric defines distance between permutations based on element-wise differences.
• Existing research has focused on determining the maximum size of permutation arrays, P(n,d), under this metric.

Purpose of the Study:

• To derive improved upper bounds for the size of permutation arrays under the Chebyshev metric.
• To introduce and analyze the concept of 'separable' arrays of strings over {0,1,2}.
• To establish a relationship between separable arrays and permutation arrays to improve existing bounds.

Main Methods:

• Defining the Chebyshev distance and permutation arrays (n,d)-PA.
• Introducing separable arrays R(n;a,b) over {0,1,2} with specific symbol counts.
• Establishing R(n;k,k) as an upper bound for P(n,n-k).
• Employing recursive and combinatorial techniques to derive bounds for R(n;a,b).

Main Results:

• Improved upper bounds for P(n,d) are established.
• The relationship R(n;k,k) ≤ P(n,n-k) is shown to be effective for k ≤ n/2.
• New bounds for R(n;a,b) were derived using novel combinatorial methods.

Conclusions:

• The study successfully improves upon known upper bounds for permutation arrays under the Chebyshev metric.
• The analysis of separable arrays provides a novel approach to bounding P(n,d).
• The derived bounds offer significant advancements in the field of combinatorial design and coding theory.