Improved Lower Bounds on the Size of Balls Over Permutations With the Infinity Metric

DOI10.1109/TIT.2017.2697423MaRDI QIDQ4566485zbMATH OpenDBLPWikidataFDO

Authors

Publication date 27 June 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.05277

Mathematics Subject Classification ID

Combinatorial codes (94B25)

Abstract: We study the size (or volume) of balls in the metric space of permutations, $S_n$, under the infinity metric. We focus on the regime of balls with radius $r=hocdot(n!-!1)$, $hoin[0,1]$, i.e., a radius that is a constant fraction of the maximum possible distance. We provide new lower bounds on the size of such balls. These new lower bounds reduce the asymptotic gap to the known upper bounds to at most $0.029$ bits per symbol. Additionally, they imply an improved ball-packing bound for error-correcting codes, and an improved upper bound on the size of optimal covering codes.

Cited in

(3)

• New lower bounds for the Hadwiger numbers of \(\ell_p\) balls for \(p<2\)
• Covering radius of permutation groups with infinity-norm
• Nonexistence of perfect permutation codes under the $$\ell _{\infty }$$-metric

This page was built for publication: Improved Lower Bounds on the Size of Balls Over Permutations With the Infinity Metric

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4566485)