|
Эта публикация цитируется в 2 научных статьях (всего в 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$.
Ключевые слова:
латинские битрейды, унитрейды, коды Рида–Маллера, комбинаторные конфигурации, булевы функции.
Поступила в редакцию: 24.12.2018 После переработки: 19.09.2019 Принята к печати: 12.11.2019
Образец цитирования:
Д. С. Кротов, В. Н. Потапов, “О спектре мощностей и числе латинских битрейдов порядка $3$”, Пробл. передачи информ., 55:4 (2019), 52–75; Problems Inform. Transmission, 55:4 (2019), 343–365
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ppi2303 https://www.mathnet.ru/rus/ppi/v55/i4/p52
|
|