Lecture: Computing Lower Bounds for Permutation Arrays under Kendall-tau Metric

Speaker: Ivan Hal Sudborough

University of Texas

Title: Computing Lower Bounds for Permutation Array under Kendall-tau Metric

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)

20:00- 21:00 (Tehran local time)

Venue link: https://zoom.us/j/94240174130?pwd=Yk0vbDhmNHZHekphM0RYSFVzYmt5dz09

Meeting ID: 942 4017 4130

Passcode: 384590

Start Date:

2023/04/04

End Date:

2023/04/30

Time:

All Rights of University of Isfahan are reserved.