Geodesic
Bounds on the cardinality of a~minimal $1$-perfect bitrade in the Hamming graph
Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 6, pp. 3-10.

Voir la notice de l'article provenant de la source Math-Net.Ru

We improve well-known upper and lower bounds on the minimal cardinality of the support of an eigenfunction of the Hamming graph $H(n,q)$ for $q>2$. In particular, the cardinality of a minimal $1$-perfect bitrade in $H(n,q)$ is estimated. We show that the cardinality of such bitrade is at least $2^{n-\frac{n-1}q}(q-2)^\frac{n-1}q$ in case $q\ge4$ and $3^\frac n2(1-O(1/n))$ in case $q=3$. Moreover, we propose a construction of bitrades of the cardinality $q^\frac{(q-2)(n-1)}q2^{\frac{n-1}q+1}$ for $n\equiv1\bmod q$ where $q$ is a prime power. Bibliogr. 10.
Keywords: Hamming graph, $1$-perfect bitrade.
Mots-clés : Krawtchouk polynomial 
@article{DA_2014_21_6_a0,
     author = {K. V. Vorob'ev and D. S. Krotov},
     title = {Bounds on the cardinality of a~minimal $1$-perfect bitrade in the {Hamming} graph},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--10},
     publisher = {mathdoc},
     volume = {21},
     number = {6},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2014_21_6_a0/}
}
TY  - JOUR
AU  - K. V. Vorob'ev
AU  - D. S. Krotov
TI  - Bounds on the cardinality of a~minimal $1$-perfect bitrade in the Hamming graph
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2014
SP  - 3
EP  - 10
VL  - 21
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2014_21_6_a0/
LA  - ru
ID  - DA_2014_21_6_a0
ER  - 
%0 Journal Article
%A K. V. Vorob'ev
%A D. S. Krotov
%T Bounds on the cardinality of a~minimal $1$-perfect bitrade in the Hamming graph
%J Diskretnyj analiz i issledovanie operacij
%D 2014
%P 3-10
%V 21
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2014_21_6_a0/
%G ru
%F DA_2014_21_6_a0
K. V. Vorob'ev; D. S. Krotov. Bounds on the cardinality of a~minimal $1$-perfect bitrade in the Hamming graph. Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 6, pp. 3-10. http://geodesic.mathdoc.fr/item/DA_2014_21_6_a0/

[1] Delsart F., Algebraicheskii podkhod k skhemam otnoshenii teorii kodirovaniya, Mir, M., 1976, 136 pp. | MR

[2] Potapov V. N., “Mnogomernye latinskie bitreidy”, Sib. mat. zhurn., 52:2 (2013), 407–416 | MR

[3] Cavenagh N. J., “The theory and application of latin bitrades: a survey”, Math. Slovaca, 58:6 (2008), 691–718 | DOI | MR | Zbl

[4] Etzion T., Vardy A., “Perfect binary codes: constructions, properties, and enumeration”, IEEE Trans. Inform. Theory, 40:3 (1994), 754–763 | DOI | MR | Zbl

[5] Hedayat A. S., Khosrovshahi G. B., “Trades”, CRC Handbook of Combinatorial Designs, Chapman and Hall/CRC, Boca Raton–London–New York, 2006, 644–648

[6] Heden O., Krotov D. S., “On the structure of non-full-rank perfect $q$-ary codes”, Adv. Math. Comm., 5:2 (2011), 149–156 | DOI | MR | Zbl

[7] Phelps K. T., “A product construction for perfect codes over arbitrary alphabets”, IEEE Trans. Inf. Theory, 30:5 (1984), 769–771 | DOI | MR | Zbl

[8] Phelps K. T., Rifà J., Villanueva M., “Kernels and $p$-kernels of $p^r$-ary 1-perfect codes”, Des. Codes Cryptogr., 37:2 (2005), 243–261 | DOI | MR | Zbl

[9] Potapov V. N., “On perfect 2-colorings of the $q$-ary $n$-cube”, Discrete Math., 312:8 (2012), 1269–1272 | DOI | MR | Zbl

[10] Solov'eva F. I., “Structure of $i$-components of perfect binary codes”, Discrete Appl. Math., 111:1–2 (2001), 189–197 | DOI | MR | Zbl