Improving the Gilbert-Varshamov bound for permutation Codes in the Cayley metric and Kendall τ-Metric

2024/04/23 by Nguyen, The · 1 citation
#05XX #94XX #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.2404.15126

Abstract

The Cayley distance between two permutations π, σ∈ S_n is the minimum number of transpositions required to obtain the permutation σ from π. When we only allow adjacent transpositions, the minimum number of such transpositions to obtain σ from π is referred to the Kendall τ-distance. A set C of permutation words of length n is called a d-Cayley permutation code if every pair of distinct permutations in C has Cayley distance at least d. A d-Kendall permutation code is defined similarly. Let C(n,d) and K(n,d) be the maximum size of a d-Cayley and a d-Kendall permutation code of length n, respectively. In this paper, we improve the Gilbert-Varshamov bound asymptotically by a factor log(n), namely C(n,d+1) ≥ Ω_d(\fracn!log nn^2d) and K(n,d+1) ≥ Ω_d((n! log n)/(n^d)). Our proof is based on graph theory techniques.

Cited by

• Permutation-Based Distances for Groups and Group-Valued Time Series

Related

• New Theoretical Bounds and Constructions of Permutation Codes under Block Permutation Metric
• New Upper Bounds on the Size of Permutation Codes under Kendall τ-Metric
• New bounds of permutation codes under Hamming metric and Kendall's τ-metric
• A New Metric on Symmetric Group and Applications to Block Permutation Codes
• Linear Programming Upper Bounds on Permutation Code Sizes From Coherent Configurations Related to the Kendall Tau Distance Metric