Improving the Gilbert-Varshamov bound for permutation Codes in the Cayley metric and Kendall $τ$-Metric
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917770071900160 |
|---|---|
| author | Nguyen, The |
| author_facet | Nguyen, The |
| contents | The Cayley distance between two permutations $π, σ\in S_n$ is the minimum number of \textit{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) \geq Ω_d\left(\frac{n!\log n}{n^{2d}}\right) \text{ and } K(n,d+1) \geq Ω_d\left(\frac{n! \log n}{n^d}\right).\] Our proof is based on graph theory techniques. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_15126 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improving the Gilbert-Varshamov bound for permutation Codes in the Cayley metric and Kendall $τ$-Metric Nguyen, The Combinatorics Discrete Mathematics Information Theory 94XX, 05XX The Cayley distance between two permutations $π, σ\in S_n$ is the minimum number of \textit{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) \geq Ω_d\left(\frac{n!\log n}{n^{2d}}\right) \text{ and } K(n,d+1) \geq Ω_d\left(\frac{n! \log n}{n^d}\right).\] Our proof is based on graph theory techniques. |
| title | Improving the Gilbert-Varshamov bound for permutation Codes in the Cayley metric and Kendall $τ$-Metric |
| topic | Combinatorics Discrete Mathematics Information Theory 94XX, 05XX |
| url | https://arxiv.org/abs/2404.15126 |