Метрические и комбинаторные свойства совершенных кодов и раскрасок тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Глава 1 Метрическая жесткость совершенных бинарных кодов

1.1 Об изометричности совершенных бинарных кодов

1.2 К строению графов минимальных расстояний совершенных бинарных (п, 3)-кодов.

1.3 О сильной изометрии бинарных кодов

Глава 2 Спектральные свойства совершенных кодов

2.1 Совершенные раскраски дистанционно-регулярных двудольных графов.

2.2 Об одном свойстве совершенных бинарных кодов

2.3 О дистанционной регулярности совершенных бинарных кодов.

Глава 3 Дефицитные раскраски и совершенные покрытия деревьями

3.1 О покрытии ребер графа одинаковыми деревьями Литература

В дискретном анализе конструкции, не допускающие улучшения, традиционно называются совершенными. К таковым относятся совершенные коды, совершенные паросочетания и др. Результаты, касающиеся таких конструкций, обычно носят фундаментальный характер и часто используются. В качестве примера приведем теорему Кенига-Холла о возможности разбиения ребер двудольного регулярного графа на совершенные паросочетания и теорему Шапиро-Злотника о независимости весового спектра совершенного кода от выбора кода и выбора кодового вектора, относительно которого этот спектр рассматривается. Построение новых совершенных конструкций, а также выявление их нетривиальных свойств является актуальной задачей.

В диссертации предпринята попытка рассмотрения с общих позиций таких математических понятий, как метрическая жесткость из геометрии, весовой спектр кода из теории кодирования и раскраска из теории графов.

Пусть М — произвольное метрическое пространство с достаточно богатой группой автоморфизмов (как минимум 2-транзитивной). Два метрических подпространства М\ и М% пространства М называются эквивалентными, если для некоторого автоморфизма А € АиЬ(М) выполняется А{М\) = Мч. Неудивительно, что практически все вопросы, связанные с метрическими подпространствами, рассматриваются с точностью до эквивалентности. Другое дело, если существо вопроса никак не зависит от того, каким образом подпространство вложено в объемлющее пространство, а важна лишь его метрическая структура. Тогда мы говорим, что не2 которое утверждение верно с точностью до изометрии. Метрические подпространства, эквивалентные любому своему изометрическому образу, называются жесткими. Научиться распознавать жесткость было бы весьма полезным делом. Сказанное выше в равной мере относится и к непрерывной, и к дискретной математике. Разница в том, что в непрерывной области исследования на эту тему ведутся давно и гораздо успешнее, чем в дискретном случае.

В главе 1, п.1., доказано (теорема 1), что при п > 15 изоме-тричность двух совершенных бинарных (п,3)-кодов влечет их эквивалентность. Тем самым опровергнута гипотеза Аб-дурахманова из [8]. Впоследствии этот результат был обобщен [14] на случай совершенных (п, 3)-кодов над д-ичным алфавитом, q > 2. В п.2. той же главы доказано, что для эквивалентности совершенных бинарных (п, 3)-кодов достаточно их слабой изометричности (теорема 2). Этот результат дает положительный ответ на вопрос К.Фелпса и М.ЛеВана из [13]. Третий параграф посвящен вопросам сильной изометрии. Доказано, что если два бинарных кода сильно изоме-тричны, то они эквивалентны.

Во второй главе исследуются совершенные раскраски дистанционно-регулярных двудольных графов — естественное обобщение совершенных кодов. Параграф 2.1. посвящен обобщению известной теоремы Шапиро и Злотника [12] об инвариантности весового спектра совершенных кодов. Аналогичная теорема оказалась верной не только для кодов, но и для всякой совершенной раскраски (если таковая существует) дистанционно-регулярного двудольного графа (аналог п-мерного куба). В параграфе 2.2. введено понятие базового множества М совершенных бинарных кодов. Согласно опре3 делению всякий такой код может быть однозначно восстановлен по пересечению с М. Доказано (теорема 5), что два средних слоя (2к — 1)-мерного куба являются базовым множеством. На этой основе получена нетривиальная верхняя оценка для числа различных совершенных бинарных кодов с расстоянием 3. Написанный на основе совместной работы автора и Ф.И.Соловьевой [4], параграф 2.3. отвечает на вопрос В.И.Левенштейна о существовании таких совершенных кодов, которые не являются дистанционно-регулярными. Доказано (теорема 6), что все совершенные бинарные (п, 3)-коды при п > 7 не являются дистанционно-регулярными.

Последняя глава содержит достаточный критерий (теорема 8) замощаемости ребер однородного двудольного графа копиями произвольного дерева с числом ребер, равным степени графа. Описан широкий класс графов, удовлетворяющих данному критерию. Это пример связи реберных замощений с правильными реберными раскрасками.

Таким образом, основными результатами диссертации являются следующие:

1. Доказано, что если два совершенных бинарных кода с расстоянием 3, тг > 15, изометричны, то они эквивалентны.

2. Доказано, что если два совершенных бинарных кода с расстоянием 3, п > 15, слабо изометричны, то они изометричны.

3. Доказано, что всякий совершенный бинарный код с расстоянием 3 можно однозначно восстановить по его пересечению с двумя средними слоями п -мерного куба.

4. Доказано, что для достаточно больших п все совершенные двоичные коды соответствующей длины не являются дистанционно-регулярными. 4

1. Августинович С. В. Об изометричности плотно упакованных бинарных кодов / / Труды института математики, СО РАН, 27 (1994) 3-5.

2. Августинович С. В. Об одном свойстве совершенных двоичных кодов // Дискретный анализ и исследование операций, 2 (3) (1995) 4-6.

3. Августинович С. В., Соловьева Ф. И. Построение совершенных двоичных кодов последовательными сдвигами ог-компонент // Пробл. передачи информ., 33 (3) (1997) 15-21.

4. Августинович С. В., Соловьева Ф. И. О дистанционной регулярности совершенных двоичных кодов // Пробл. передачи информ., 34 (3) (1998) 47-49.

5. Августинович С. В. О разбиении множества ребер графа на изоморфные деревья // Дискретный анализ и исследование операций, 4 (1) 4 (1997) 3-5.

6. Августинович С. В. К строению графов минимальных расстояний совершенных бинарных (п,3)-кодов // Дискретный анализ и исследование операций, 1 (5) 4 (1998) 3-5.

7. Августинович С. В., Соловьева Ф. И. О несистематических совершенных двоичных кодах // Пробл. передачи информ. 32 (3) (1996) 47-50.31

8. Абдурахманов Ж. К. О геометрической структуре кодов, исправляющих ошибки: Дис. . канд. физ.-мат. наук: 01.01.09. Ташкент, 1991, С. 66.

9. Васильев Ю. JI. О негрупповых плотно упакованных кодах // Проблемы кибернетики. М.: Наука, 8 (1962) 337339.

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

11. Харари Ф. Теория графов. М.: Мир, 1973.

12. Шапиро Г. С., Злотник Д. Л. К математической теории кодов с исправлением ошибок // Кибернетический сб. 5 (1962) 7-32.

13. Phelps К. Т., Le Van М. Т. Switching Equivalence Classes of Perfect Codes // Designs, Codes and Cryptography, 16 (2) (1999) 179-184.

14. Solov'eva F. IAvgustinovich S. V., Honold T. and Heise W. On the extendability of code isomstries // Journal of Geometry, 61 (1998) 3-16.

15. Визит В. Г. Дистрибутивная раскраска вершин графа. // Дискретный анализ и исследование операций,2 (4) (1995) 3-12.