RUS  ENG
Полная версия
ЖУРНАЛЫ // Проблемы передачи информации // Архив

Пробл. передачи информ., 2019, том 55, выпуск 4, страницы 52–75 (Mi ppi2303)

Эта публикация цитируется в 2 статьях

Теория кодирования

О спектре мощностей и числе латинских битрейдов порядка $3$

Д. С. Кротов, В. Н. Потапов

Институт математики им. С.Л. Соболева СО РАН, Новосибирск

Аннотация: Унитрейдом (латинским) порядка $k$ называется подмножество вершин графа Хэмминга $H(n,k)$, которое либо пересекается по двум вершинам, либо совсем не пересекается с любой максимальной кликой. Битрейдом называется двудольный, т.е. разделяющийся на два независимых подмножества, унитрейд. Исследуется спектр мощностей битрейдов в графе Хэмминга $H(n,k)$ при $k=3$ (троичном гиперкубе) и рост числа таких битрейдов с ростом $n$. В частности, определены все возможные малые (до $2{,}5\cdot 2^n$) и большие (от $14\cdot 3^{n-3}$) мощности битрейдов размерности $n$ и доказано, что мощность битрейда принимает значения, только сравнимые с $0$ или $2^n$ по модулю $3$ (этот результат имеет трактовку в терминах троичного кода типа Рида–Маллера). Часть результатов применима для произвольного $k$. Доказано, что при $k=3$ и растущем $n$ число неэквивалентных битрейдов не меньше $2^{(2/3-o(1))n}$ и не больше $2^{\alpha^n}$, $\alpha<2$ (порядок роста двойного логарифма от этого числа остается неизвестным). Альтернативно исследуемое множество $B_n$ битрейдов порядка $3$ можно определить следующим образом: $B_0$ состоит из трех чисел $-1,0,1$; $B_n$ состоит из всех упорядоченных троек $(a,b,c)$ элементов из $B_{n-1}$, таких что $a+b+c=0$.

Ключевые слова: латинские битрейды, унитрейды, коды Рида–Маллера, комбинаторные конфигурации, булевы функции.

УДК: 621.391.1 : 519.1

Поступила в редакцию: 24.12.2018
После переработки: 19.09.2019
Принята к печати: 12.11.2019

DOI: 10.1134/S0555292319040028


 Англоязычная версия: Problems of Information Transmission, 2019, 55:4, 343–365

Реферативные базы данных:


© МИАН, 2024