Том 20, номер 3, 2013 г., Стр. 3-25

УДК 519.87
Ковалевская Д. И., Соловьёва Ф. И., Филимонова Е. С.
O системах троек Штейнера малого ранга, вложимых в совершенные двоичные коды

Аннотация:
Свитчинговым методом получена классификация систем троек Штейнера $\mathrm{STS}(n)$ порядка $n=2^r-1$, $r>3$, малого ранга $r_n$ (на 2 отличного от ранга кода Хэмминга длины $n$), вложимых в совершенные двоичные коды длины $n$ такого же ранга. Приведены верхняя и нижняя оценки числа различных таких $\mathrm{STS}$. Дано описание класса систем $\mathrm{STS}(n)$ ранга $r_n$, не вложимых в совершенные двоичные коды длины $n$ такого же ранга, и приведена нижняя оценка числа этих систем. Доказана вложимость любой системы $\mathrm{STS}(n)$ ранга $r_n-1$ в совершенный код Васильева длины $n$ такого же ранга.
Библиогр. 22.

Ключевые слова: система троек Штейнера, совершенный двоичный код, свитчинг, Паш-конфигурация, $ijk$-компонента, $i$-компонента.

Ковалевская Дарья Игоревна ¹
Соловьёва Фаина Ивановна ^1,2
Филимонова Елена Сергеевна ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: daryik@rambler.ru, sol@math.nsc.ru, filimones@rambler.ru

Статья поступила 2 августа 2012 г.
Исправленный вариант — 20 марта 2013 г.

Литература

[1] Августинович С. В., Соловьёва Ф. И. О несистематических совершенных кодах // Пробл. передачи информ. - 1996. - Т. 32, № 3. - С. 47–50.

[2] Августинович С. В., Соловьёва Ф. И. Построение совершенных двоичных кодов последовательными сдвигами $\tilde\alpha$-компонент // Пробл. передачи информ. - 1997. - Т. 33, № 3. - С. 15–21.

[3] Васильев Ю. Л. О негрупповых плотно-упакованных кодах // Пробл. кибернетики. - 1962. - Вып. 8. - С. 337–339.

[4] Егорычев Г. П. Доказательство гипотезы Ван дер Вардена для перманентов // Сиб. мат. журн. - 1981. - Т. 22, № 6. - С. 65–71.

[5] Зиновьев В. А., Зиновьев Д. В. О кодах Васильева длины $n=2^m$ и удвоение систем Штейнера $S(n,4,3)$ заданного ранга // Пробл. передачи информ. - 2006. - Т. 42, вып. 1. - С. 13–33.

[6] Зиновьев В. А., Зиновьев Д. В. Системы Штейнера S(v, k, k−1): компоненты и ранг // Пробл. передачи информ. - 2011. - Т. 47, № 2. - C. 52–71.

[7] Кротов Д. С., Потапов В. Н. О свитчинговой эквивалентности n-арных квазигрупп порядка 4 и совершенных двоичных кодов // Пробл. передачи информ. - 2010. - Т. 46, № 3. - C. 22–28.

[8] Мак-Вильямс Ф. Дж., Слоэн Н. Дж. Теория кодов, исправляющих ошибки. - М.: Связь, 1979. - 744 c.

[9] Петренюк А. Я. Признаки неизоморфности систем троек Штейнера // Укр. мат. журн. - 1972. - Т. 24, № 6. - C. 772–780.

[10] Соловьёва Ф. И., Топалова С. Т. Совершенные двоичные коды и системы троек Штейнера с максимальными порядками групп автоморфизмов // Дискрет. анализ и исслед. операций. Сер. 1. - 2000. - Т. 7, № 4. - С. 101–110.

[11] Холл M. Комбинаторика. - М.: Мир, 1970. - 424 c.

[12] Assmus E. F., Mattson H. F. Jr. On tactical configurations and error correcting codes // J. Comb. Theory. - 1967. - Vol. 2. - P. 243–257.

[13] Kaski P., Östergård P. R. J. The Steiner triple systems of order 19 // Math. Comput. - 2004. - Vol. 73. - P. 2075–2092.

[14] Kovalevskaya D. I., Filimonova E. S., Solov’eva F. I. Steiner triple (quadruple) systems of small ranks embedded into perfect (extended perfect) binary codes // Proc. 13th Int. Workshop .Algebraic and combinatorial coding theory. (Pomorie, Bulgaria, June 15–21, 2012). - Pomorie: Inst. Math. Informatics, Bulg. Acad. Sci., 2012. - P. 203–208.

[15] Linial N., Luria Z. An upper bound on the number of Steiner triple systems // Random Structures & Algorithms, accepted, 2013. DOI: 10.1002/rsa.20487.

[16] Östergård P. R. J., Pottonen O. The perfect binary one-error-correcting codes of length 15. Part 1. - Classification // IEEE Trans. Inform. Theory. - 2009. - Vol. 55. - P. 4657–4660.

[17] Östergård P. R. J., Pottonen O. There exist Steiner triple systems of order 15 that do not occur in a perfect binary one-error-correcting code // J. Comb. Des. - 2007. - Vol. 15. - P. 465–468.

[18] Solov’eva F. I. On perfect codes and related topics // Com²Mac Lect. Notes. Ser. 13. - Pohang, Korea: Pohang Univ. Sci. Tech., 2004. - 80 p.

[19] Solov’eva F. I., Avgustinovich S. V., Heden O. The classification of some perfect codes // Des. Codes Cryptogr. - 2004. - Vol. 31, N 3. - P. 313–318.

[20] Tonchev V. D. A mass formula for Steiner triple systems $STS(2^n-1)$ of $2$-rank $2^n-n$ // J. Comb. Theory. Ser. A. - 2001. - Vol. 95. - P. 197–208.

[21] Zinoviev D. V., Zinoviev V. A. Steiner triple systems $S(2^m-1,3,2)$ of $2$-rank $r\leq2^m-m+1$: construction and properties, Proc. 13th Int. Workshop Algebraic and combinatorial coding theory. (Pomorie, Bulgaria, June 15–21, 2012). - Pomorie: Inst. Math. Informatics, Bulg. Acad. Sci., 2012. -
P. 358-363.

[22] Zinoviev V. A., Zinoviev D. V. Steiner triple systems $S(2^m-1,3,2)$ of rank $2^m-m+1$ over $F_2$ // Probl. Inform. Transm. - 2012. - Vol. 48, N 2. - P. 102–126.