Abstract
A permutation code of length n and distance d is a set Γ of permutations from some fixed set of n symbols such that the Hamming distance between each distinct x,y∈Γ is at least d. In this note, we determine some new results on the maximum size of a permutation code with distance equal to 4, the smallest interesting value. The upper bound is improved for almost all n via an optimization problem on Young diagrams. A new recursive construction improves known lower bounds for small values of n.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Brouwer, A.E., Shearer, J.B., Sloane, N.J.A., Smith, W.D.: A new table of constant weight codes. IEEE Trans. Inform. Theory 36, 1334–1380 (1990)
Chu, W., Colbourn, C.J., Dukes, P.J.: Permutation codes for powerline communication. Des. Codes Cryptography 32, 51–64 (2004)
Colbourn, C.J., Kløve, T., Ling, A.C.H.: Permutation arrays for powerline communication and mutually orthogonal Latin squares. IEEE Trans. Inform. Theory 50, 1289–1291 (2004)
Delsarte, P.: An algebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl. 10 (1973)
Deza, M., Vanstone, S.A.: Bounds for permutation arrays. J. Statist. Plann. Inference 2, 197–209 (1978)
Ellis, D., Friedgut, E., Pilpel, H.: Intersecting families of permutations. Preprint
Fulton, W.: Young Tableaux. London Mathematical Society Student Texts, vol. 35. Cambridge University Press, Cambridge (1997)
Frankl, P., Deza, M.: On the maximum number of permutations with given maximal or minimal distance. J. Combin. Theory Ser. A 22, 352–360 (1977)
Graham, R.L., Sloane, N.J.A.: Lower bounds for constant weight codes. IEEE Trans. Inform. Theory 26, 37–43 (1980)
Keevash, P., Ku, C.Y.: A random construction for permutation codes and the covering radius. Des. Codes Cryptogr. 41, 79–86 (2006)
Murnaghan, F.D.: The Theory of Group Representations. Johns Hopkins Press, Baltimore (1938)
Schrijver, A.: A comparison of the Delsarte and Lovász bounds. IEEE Trans. Inform. Theory 25, 425–429 (1979)
Tarnanen, H.: Upper bounds on permutation codes via linear programming. European J. Combin. 20, 101–114 (1999)
Van Pul, C.L.M., Etzion, T.: New lower bounds for constant weight codes. IEEE Trans. Inform. Theory 35, 1324–1329 (1989)
Yang, L., Chen, K.: New lower bounds on sizes of permutation arrays. Preprint
Author information
Authors and Affiliations
Corresponding author
Additional information
This research is supported by NSERC.
Rights and permissions
About this article
Cite this article
Dukes, P., Sawchuck, N. Bounds on permutation codes of distance four. J Algebr Comb 31, 143–158 (2010). https://doi.org/10.1007/s10801-009-0191-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10801-009-0191-2