Собственные функции и кратные совершенные коды в графах Джонсона и Хэмминга

• Автор: Воробьёв, Константин Васильевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Новосибирск
• Количество страниц: 52 с. : ил.

Оглавление
Введение
1 Совершенные 2-раскраски гиперкуба
1.1 Основные определения и понятия
1.2 Известные конструкции
1.3 Итеративная конструкция и новые оценки на число совершенных 2-раскрасок гиперкуба
2 Кратные совершенные коды в гиперкубе
2.1 Основные определения и понятия
2.2 Связь совершенных 2-раскрасок и /г-кратных совершенных кодов
2.3 Некоторые частные случаи
3 Собственные функции в графах Джонсона и Хэмминга
3.1 Основные определения и понятия
3.2 Действие преобразования Фурье на собственные функции графа Джонсона
3.3 Критерий вложимости собственных функций графа Джонсона
в собственные функции графа Хэмминга
3.4 Специальный случай критерия вложимости
Литература

Введение
В настоящей диссертации исследуются проблемы существования и перечисления объектов, находящихся на стыке алгебраической комбинаторики, теории кодов, исправляющих ошибки в канале связи с шумами, и теории графов. Предметом исследования данной работы являются собственные функции графов Джонсона и Хэмминга, а также кратные совершенные коды и совершенные раскраски графа Хэмминга.
Вершинами графа п-мерного куба (или двоичного графа Хэмминга) являются все двоичные наборы длины та; вершины смежны, если соответствующие им наборы отличаются ровно в одной координате. Весом wt(y) вершины у G Нп называется количество единиц в этом наборе. Расстояние Хэмминга d(x,y) между вершинами ïj 6 Н„ - это количество позиций, в которых х и у различны.
Графом Джонсона J(n:w) называется граф, вершинами которого являются все двоичные наборы, содержащие в точности w единиц. Две вершины являются смежными, если соответствующие им наборы отличаются ровно в двух координатах. Расстояние между двумя вершинами ж, у G J(n,w) определяется следующим образом: d.j(x,y) = тф#(ж,у). Заданные выше расстояния dj(x,y) и dn(x,y) являются стандартными графскими метриками, то есть равны числу ребер в минимальном пути из х в у в графах J(n,w) и Н" соответственно.
Отображение Т : V —> (1,2, ...к} называется совершенной раскраской вершин графа G = (V, Е) в к цветов (совершенной fc-раскраской) с матрицей М = (m,j)fc}, если оно сюръективно и для каждых i,j у любой вершины цвета i число соседей цвета j равно тгу. Матрица A4 пазывает-

ся матрицей параметров совершенной раскраски. В зарубежной литературе разбиение вершин графа на цвета, соответствующее совершенной раскраске, называют equitable partition. Прямым образом из определения следует, что
1-совсршенные коды в произвольном графе также являются совершенными
2-раскрасками этого графа.
Одной из основных проблем дискретной математики и теории кодирования является проблема построения объектов с заданными свойствами. Вопросы существования и построения таких структур, как блок-схемы, совершенные коды и раскраски различных графов, на протяжение долгих лег привлекают внимание многих известных математиков. В таких исследованиях можно выделить 2 основных направления: поиск различных необходимых условий существования искомого объекта и построение конструкций, которые позволяют получать нижние оценки на число различных или неизоморфпых объектов с заданными параметрами.
Исследованиями, посвященными совершенным 2-раскраскам «-мерного булева куба, занимался Д.Г. Фон-Дер-Флаасс. В работе 2007 года [1] были получены первые необходимые условия на параметры возможных совершенных 2-раскрасок. Позднее этим же автором была получена так называемая граница корреляционной иммунности [2], которая позволила сформулировать существенное ограничение на параметры существующих совершенных
2-раскрасок п-куба. Раскраски, достигающие эту границу в 12-мерном кубе, были впоследствии изучены Д.Г. Фоп-Дер-Флаассом в [3].
В силу того, что совершенная 2-раскраска графа являются обобщением понятия 1-совершенного кода, проблема подсчета различных 2-раскрасок с заданной матрицей параметров сложнее, чем аналогичная проблема для 1-совершенных кодов. Поскольку теория совершенных кодов насчитывает уже более полувека, существует ряд конструкций и нижних оценок на число 1-совсршенных кодов в кубе заданной размерности.
Первые совершенные коды были построены Р. Хэммингом в 1950 году [4]. Зиновьев, Леонтьев и Тиетвайнен показали |5. б], что все возможные параметры 1-совершенных кодов исчерпываются списком п — 2к — 1 ,г = 1 и п = 23, г = 3 для двоичного n-куба. В 1962 году Ю.Л. Васильевым

совершенными кодами радиуса 3. Второе уравнение можно преобразовать следующим образом:
2{Ь + с) — 1 ± ^/12(6 + с) - 23 п _ 2 ,
и поиск кратных совершенных кодов радиуса 3 сводится к поиску решений этого уравнения в натуральных числах, удовлетворяющих (1.2).
В заключение в качестве примера приведем все совершенные раскраски, являющиеся кратными совершенными кодами радиуса 2 в 10-мерном кубе:
/з7/4б/55/б4 ^19уу28уу37у
Им соответствуют кратности 7,14,21,28. На сегодняшний день существуют конструкции, позволяющие строить большое число различных совершенных раскрасок с различными параметрами (31, 27]. Приведенные выше результаты позволяют искать среди них неизвестные ранее кратные совершенные коды. Описанные в главе определения и задачи легко переносятся и на другие классы графов, такие как кубические транзитивные, циркулярные и графы Джонсона.