Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Permutation Codes

preprint2013arXivOpen access

Abstract

Given positive integers nn and dd, let M(n,d)M(n,d) denote the maximum size of a permutation code of length nn and minimum Hamming distance dd. The Gilbert-Varshamov bound asserts that M(n,d)≥n!/V(n,d−1)M(n,d) \geq n!/V(n,d-1) where V(n,d)V(n,d) is the volume of a Hamming sphere of radius dd in §n§_n. Recently, Gao, Yang, and Ge showed that this bound can be improved by a factor Ω(log⁡n)Ω(\log n), when dd is fixed and n→∞n \to \infty. Herein, we consider the situation where the ratio d/nd/n is fixed and improve the Gilbert-Varshamov bound by a factor that is \emph{linear in nn}. That is, we show that if d/n<0.5d/n < 0.5, then M(n,d)≥cn n!V(n,d−1) M(n,d)\geq cn\,\frac{n!}{V(n,d-1)} where cc is a positive constant that depends only on d/nd/n. To establish this result, we follow the method of Jiang and Vardy. Namely, we recast the problem of bounding M(n,d)M(n,d) into a graph-theoretic framework and prove that the resulting graph is locally sparse.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.