Abstract
We analyse a probabilistic argument that gives a semi-random construction for a permutation code on n symbols with distance n − s and size Θ(s!(log n)1/2), and a bound on the covering radius for sets of permutations in terms of a certain frequency parameter.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N Alon J Spencer (2000) The probabilistic method EditionNumber2 Wiley-Interscience [John Wiley & Sons] New York Occurrence Handle0996.05001 Occurrence Handle10.1002/0471722154
Babai L, Frankl P (1992) Linear algebra methods in combinatorics. Department of Computer Science, University of Chicago, Preliminary version
PJ Cameron CY Ku (2003) ArticleTitleIntersecting families of permutations Euro J Combin 24 881–890 Occurrence Handle1026.05001 Occurrence Handle2009400 Occurrence Handle10.1016/S0195-6698(03)00078-7
PJ Cameron IM Wanless (2005) ArticleTitleCovering radius for sets of permutations Disc Math 293 91–109 Occurrence Handle1078.05001 Occurrence Handle2136054 Occurrence Handle10.1016/j.disc.2004.08.024
W Chu CJ Colbourn P Dukes (2004) ArticleTitleConstructions for permutation codes in powerline communications Des Codes Cryptogr 32 51–64 Occurrence Handle1065.94003 Occurrence Handle2072316 Occurrence Handle10.1023/B:DESI.0000029212.52214.71
M Deza P Mrankl (1977) ArticleTitleOn the maximum number of permutations with given maximal or minimal distance J Combin Theory Ser A 22 352–360 Occurrence Handle10.1016/0097-3165(77)90009-7
C Ding F-W Fu T Klve VK-W Wei (2002) ArticleTitleConstructions of permutation arrays IEEE Trans Inform Theory 48 977–980 Occurrence Handle1061.05016 Occurrence Handle1908460 Occurrence Handle10.1109/18.992812
P Erdős C Ko R Rado (1961) ArticleTitleIntersection theorems for systems of finite sets Quart J Math Oxford Ser 12 313–320 Occurrence Handle140419
P Erdős J Spencer (1991) ArticleTitleLopsided Lovász local lemma and Latin transversals Disc Appl Math 30 151–154 Occurrence Handle10.1016/0166-218X(91)90040-4
P Frankl (1995) Extremal set systems RL Graham M Grotschel L Lovasz (Eds) Handbook of combinatorics Elsevier Amsterdam 1293–1329
F-W Fu T Kløve (2004) ArticleTitleTwo constructions of permutation arrays IEEE Trans Inform Theory 50 881–883 Occurrence Handle2090598 Occurrence Handle10.1109/TIT.2004.826659
Kézdy AE, Snevily HS, unpublished manuscript
FJ MacWilliams NJA Sloane (1977) The theory of error-correcting codes North-Holland Amsterdam Occurrence Handle0657.94010
N Pavlidou AJH Vinck J Yazdani B Honary (2003) ArticleTitlePower line communications: state of the art and future trends IEEE Commun Mag 41 IssueIDissue 4 34–40 Occurrence Handle10.1109/MCOM.2003.1193972
H Tarnanen (1999) ArticleTitleUpper bounds on permutation codes via linear programming Euro J Combin 20 101–114 Occurrence Handle0915.94010 Occurrence Handle1669620 Occurrence Handle10.1006/eujc.1998.0272
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by C. J. Colbourn.
Rights and permissions
About this article
Cite this article
Keevash, P., Ku, C.Y. A random construction for permutation codes and the covering radius. Des Codes Crypt 41, 79–86 (2006). https://doi.org/10.1007/s10623-006-0017-3
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10623-006-0017-3