Semidefinite programming for permutation codes

被引：2

作者：

Bogaerts, Mathieu ^{[1
]}

Dukes, Peter ^{[2
]}

机构：

[1] Univ Libre Bruxelles, Fac Sci Appl, Brussels, Belgium

[2] Univ Victoria, Dept Math & Stat, Victoria, BC, Canada

来源：

DISCRETE MATHEMATICS | 2014年 / 326卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

Symmetric group; Permutation code; Terwilliger algebra; Semidefinite programming; UPPER-BOUNDS;

D O I：

10.1016/j.disc.2014.03.002

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We initiate study of the Terwilliger algebra and related semidefinite programming techniques for the conjugacy scheme of the symmetric group Sym(n). In particular, we compute orbits of ordered pairs on Sym(n) acted upon by conjugation and inversion, explore a block diagonalization of the associated algebra, and obtain improved upper bounds on the size M(n, D) of permutation codes of lengths n = 6, 7. For instance, these techniques detect the nonexistence of the projective plane of order six via M(6, 5) < 30 and yield a new upper bound M(7, 4) < 535 for a challenging open case. Each of these represents an improvement on earlier Delsarte linear programming results. (C) 2014 Elsevier B.V. All rights reserved.

引用

页码：34 / 43

页数：10

共 24 条

[1]

[Anonymous], PHILIPS RES REP S

[2]

Balmaceda JMP., 1994, KYUSHU J MATH, V48, P221, DOI 10.2206/kyushujm.48.221

[3]

Bogaerts M, 2010, ELECTRON J COMB, V17

[4] Covering radius for sets of permutations [J].

Cameron, PJ ;

Wanless, IM .

DISCRETE MATHEMATICS, 2005, 293 (1-3) :91-109

[5] Intersecting families of permutations [J].

Cameron, PJ ;

Ku, CY .

EUROPEAN JOURNAL OF COMBINATORICS, 2003, 24 (07) :881-890

[6] On constant composition codes [J].

Chu, WS ;

Colbourn, CJ ;

Dukes, P .

DISCRETE APPLIED MATHEMATICS, 2006, 154 (06) :912-929

[7] Constructions for permutation codes in powerline communications [J].

Chu, WS ;

Colbourn, CJ ;

Dukes, P .

DESIGNS CODES AND CRYPTOGRAPHY, 2004, 32 (1-3) :51-64

[8] Permutation arrays for powerline communication and mutually orthogonal Latin squares [J].

Colbourn, CJ ;

Klove, T ;

Ling, ACH .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2004, 50 (06) :1289-1291

[9] Numerical block diagonalization of matrix *-algebras with application to semidefinite programming [J].

de Klerk, Etienne ;

Dobre, Cristian ;

Pasechnik, Dmitrii V. .

MATHEMATICAL PROGRAMMING, 2011, 129 (01) :91-111

[10] BOUNDS FOR PERMUTATION ARRAYS [J].

DEZA, M ;

VANSTONE, SA .

JOURNAL OF STATISTICAL PLANNING AND INFERENCE, 1978, 2 (02) :197-209

← 1 2 3 →