Remoteness of permutation codes

DOI10.1016/J.EJC.2012.03.027MaRDI QIDQ427818zbMATH OpenOpenAlexFDO

Authors Peter J. Cameron, Maximilien Gadouleau

Publication date 18 June 2012

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

covering radiusremotenesspermutation groupspermutation codestransitive groupsstability number of related graph

Mathematics Subject Classification ID

General theory for finite permutation groups (20B05) Linear codes (general theory) (94B05) Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75)

Abstract: In this paper, we introduce a new parameter of a code, referred to as the remoteness, which can be viewed as a dual to the covering radius. Indeed, the remoteness is the minimum radius needed for a single ball to cover all codewords. After giving some general results about the remoteness, we then focus on the remoteness of permutation codes. We first derive upper and lower bounds on the minimum cardinality of a code with a given remoteness. We then study the remoteness of permutation groups. We show that the remoteness of transitive groups can only take two values, and we determine the remoteness of transitive groups of odd order. We finally show that the problem of determining the remoteness of a given transitive group is equivalent to determining the stability number of a related graph.

Recommendations

• The remoteness of the permutation code of the group \(U_{6n}\)
• On the perturbation code of the group \(V_{8n}\) and its parameters
• Equidistant permutation group codes
• Permutation codes with specified packing radius
• Bounds on permutation codes of distance four

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 124521 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 686998 (Why is no real title available?)
• scientific article; zbMATH DE number 1024657 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• A Tight Analysis of the Greedy Algorithm for Set Cover
• Complete mappings of finite groups
• Covering radius for sets of permutations
• Graph theory
• Permutation codes
• Reduction of the Hall-Paige conjecture to sporadic simple groups.
• The admissibility of sporadic simple groups.
• The existence of Latin squares without orthogonal mates
• Tight upper bounds for the domination numbers of graphs with given order and minimum degree

Cited in

(7)

• The remoteness of the permutation code of the group \(U_{6n}\)
• The covering radius problem for sets of 1-factors of the complete uniform hypergraphs
• Equidistant permutation group codes
• On the perturbation code of the group \(V_{8n}\) and its parameters
• Infinity-norm permutation covering codes from cyclic groups
• New constructions and bounds for Winkler's hat game
• Finite dynamical systems, hat games, and coding theory

This page was built for publication: Remoteness of permutation codes

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