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

Пробл. передачи информ., 2011, том 47, выпуск 2, страницы 52–71 (Mi ppi2045)

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

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

Системы Штейнера $S(v,k,k-1)$: компоненты и ранг

В. А. Зиновьев, Д. В. Зиновьев

Институт проблем передачи информации им. А. А. Харкевича РАН

Аннотация: Для произвольной системы Штейнера $S(v,k,t)$ введено понятие компоненты как подмножества системы, которое может быть преобразовано (заменено другим подмножеством) без потери свойства результирующего множества быть системой Штейнера $S(v,k,t)$. Таким образом, компонента позволяет строить новые системы Штейнера с такими же параметрами, как и исходная система. Получены два рекурсивных метода построения бесконечных семейств компонент (как с растущим, так и с фиксированным $k$) для произвольной системы Штейнера $S(v,k,k-1)$. Рассмотрены примеры таких компонент для систем троек Штейнера $S(v,3,2)$, а также для систем четверок Штейнера $S(v,4,3)$. Для таких систем и для специального типа так называемых нормальных компонент найдено необходимое и достаточное условие, при котором $2$-ранг системы (т.е. ранг над полем $\mathbb F_2$) повышается при свитчинге компоненты. Доказано, что для $k\ge5$ произвольные системы Штейнера $S(v,k,k-1)$ и $S(v,k,k-2)$ имеют максимально возможные $2$-ранги.

УДК: 621.391.1+519.7

Поступила в редакцию: 20.10.2009
После переработки: 18.01.2011


 Англоязычная версия: Problems of Information Transmission, 2011, 47:2, 130–148

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


© МИАН, 2024