Эта публикация цитируется в
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