Constructing permutation arrays using partition and extension (Q2291664)

Let \(n > d\) be positive integers and \(M(n, d)\) be the largest number of permutations on \(n\) symbols with pairwise Hamming distance at least \(d\). Finding better bounds on \(M(n, d)\) is an interesting combinatorial problem. A universally applicable technique, partition and extension, was introduced recently by the authors to construct sets of permutations on \(n\) symbols with pairwise Hamming distance \(d\). These sets of large sizes were proposed for power-line communication. In this paper, several new computational methods for the partition and extension technique were presented, which produced several competitive new lower bounds on \(M(n, d)\) for various integers \(n\) and \(d\). Among them, the sequential partition and extension is an improvement which uses iteration to extend permutation arrays (PAs) by two or more symbols. The parallel partition and extension introduces several new symbols simultaneously, which can give new lower bounds for \(M (n + r , d )\) by extending PAs on \(n\) symbols with Hamming distance \(d- r\). A modification of the Kronecker product operation on PAs can be used to create larger PAs suitable for simple partition and extension. Moreover, two efficient algorithms for computing new partitions (an iterative greedy algorithm and an algorithm based on integer linear programming) were also presented. Experimental results provide new lower bounds for \(M(n, n -1)\), for many integers \( n< 600\).