Abstract: Permutation arrays under the Kendall-tau metric have been considered for

error-correcting codes. For two permutations P and Q, the Kendall-tau distance

between P and Q is the minimum number of adjacent transpositions (bubble sort

operations) to transform P into Q. Given n and d in [1,(n 2)], the task is to find a large

permutation array on n symbols with pairwise Kendall-tau distance at least d. Let

P(n,d) denote the maximum size of any permutation array of permutations on n

symbols with pairwise Kendall-tau distance d. Using new recursive techniques, new

automorphisms, and programs that combine randomness and greedy strategies, we

obtain several improved lower bounds for P(n,d).

 

Time: Thursday, April 13, 2023 (24 Farvardin 1402)