Bounds on permutation codes of distance four
P. Dukes
and N. Sawchuck
Department of Mathematics and Statistics, University of Victoria, Victoria, BC V8W 3R4, Canada
DOI: 10.1007/s10801-009-0191-2
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\in Γ 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.
Pages: 143–158
Keywords: keywords symmetric group; permutation code; permutation array; characters; Young diagram; linear programming
Full Text: PDF
References
1. 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)
2. Chu, W., Colbourn, C.J., Dukes, P.J.: Permutation codes for powerline communication. Des. Codes Cryptography 32, 51-64 (2004)
3. 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)
4. Delsarte, P.: An algebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl. 10 (1973)
5. Deza, M., Vanstone, S.A.: Bounds for permutation arrays. J. Statist. Plann. Inference 2, 197-209 (1978)
6. Ellis, D., Friedgut, E., Pilpel, H.: Intersecting families of permutations. Preprint
7. Fulton, W.: Young Tableaux. London Mathematical Society Student Texts, vol.
35. Cambridge University Press, Cambridge (1997)
8. 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) J Algebr Comb (2010) 31: 143-158
9. Graham, R.L., Sloane, N.J.A.: Lower bounds for constant weight codes. IEEE Trans. Inform. Theory 26, 37-43 (1980)
10. Keevash, P., Ku, C.Y.: A random construction for permutation codes and the covering radius. Des.
2. Chu, W., Colbourn, C.J., Dukes, P.J.: Permutation codes for powerline communication. Des. Codes Cryptography 32, 51-64 (2004)
3. 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)
4. Delsarte, P.: An algebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl. 10 (1973)
5. Deza, M., Vanstone, S.A.: Bounds for permutation arrays. J. Statist. Plann. Inference 2, 197-209 (1978)
6. Ellis, D., Friedgut, E., Pilpel, H.: Intersecting families of permutations. Preprint
7. Fulton, W.: Young Tableaux. London Mathematical Society Student Texts, vol.
35. Cambridge University Press, Cambridge (1997)
8. 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) J Algebr Comb (2010) 31: 143-158
9. Graham, R.L., Sloane, N.J.A.: Lower bounds for constant weight codes. IEEE Trans. Inform. Theory 26, 37-43 (1980)
10. Keevash, P., Ku, C.Y.: A random construction for permutation codes and the covering radius. Des.