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

Cite: Кротов Д.С. , Потапов В.Н.
О спектре мощностей и числе латинских битрейдов порядка 3
Проблемы передачи информации. 2019. Т.55. №4. С.52-75. DOI: 10.1134/s0555292319040028 РИНЦ OpenAlex

Translated: Krotov D.S. , Potapov V.N.
On the Cardinality Spectrum and the Number of Latin Bitrades of Order 3
Problems of Information Transmission. 2019. V.55. N4. P.343-365. DOI: 10.1134/s0032946019040021 WOS Scopus РИНЦ OpenAlex

Dates:

Submitted:	Dec 24, 2018
Accepted:	Nov 12, 2019

Identifiers:

Elibrary:	41384878
OpenAlex:	W2991187046

Citing:

DB	Citing
Elibrary	1

Altmetrics: