Том 21, номер 6, 2014 г., Стр. 3-10

УДК 519.1
Воробьёв К. В., Кротов Д. С.
Оценки мощности минимального 1-совершенного битрейда в графе Хэмминга

Аннотация:
Улучшены известные нижняя и верхняя оценки на минимальную мощность носителя собственной функции графа Хэмминга $H(n,q)$, где $q>2$. В частности, оценена мощность минимального $1$-совершенного битрейда в $H(n,q)$. Показано, что мощность такого битрейда ограничена снизу величиной $2^{n-\frac{n-1}q}(q-2)^\frac{n-1}q$ в случае $q\ge4$ и $3^\frac n2(1-O(1/n))$ в случае $q=3$. Кроме того, предложена конструкция, позволяющая строить битрейды мощности $q^\frac{(q-2)(n-1)}q2^{\frac{n-1}q+1}$ при $n\equiv1\bmod q$, где $q$ – степень простого числа.
Библиогр. 10.

Ключевые слова: граф Хэмминга, полином Кравчука, 1-совершенный битрейд.

Воробьёв Константин Васильевич ^1,2
Кротов Денис Станиславович ^1,2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: vorobev@math.nsc.ru, krotov@math.nsc.ru

Статья поступила 23 октября 2014 г.
Исправленный вариант — 10 ноября 2014 г.

Литература

[1] Дельсарт Ф. Алгебраический подход к схемам отношений теории кодирования. - М.: Мир, 1976. - 136 c.

[2] Потапов В. Н. Многомерные латинские битрейды // Сиб. мат. журн. - 2013. - Т. 52, №2. - С. 317–324.

[3] Cavenagh N. J. The theory and application of latin bitrades: a survey // Math. Slovaca. - 2008. - Vol. 58, N6. - P. 691–718.

[4] Etzion T., Vardy A. Perfect binary codes: constructions, properties, and enumeration // IEEE Trans. Inform. Theory. - 1994. - Vol. 40, N3. - P. 754–763.

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

[6] Heden O., Krotov D. S. On the structure of non-full-rank perfect q-ary codes // Adv. Math. Comm. - 2011. - Vol. 5, N2. - P. 149–156.

[7] Phelps K. T. A product construction for perfect codes over arbitrary alphabets // IEEE Trans. Inf. Theory. - 1984. - Vol. 30, N5. - P. 769–771.

[8] Phelps K. T., Rif`a J., Villanueva M. Kernels and p-kernels of pr-ary 1-perfect codes // Des. Codes Cryptogr. - 2005. - Vol. 37, N2. - P. 243–261.

[9] Potapov V. N. On perfect 2-colorings of the q-ary n-cube // Discrete Math. - 2012. - Vol. 312, N8. - P. 1269–1272.

[10] Solov’eva F. I. Structure of i-components of perfect binary codes // Discrete Appl. Math. - 2001. - Vol. 111, N1–2. - P. 189–197.