Совершенные 2-раскраски графов Джонсона тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

00460.3788

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ им. С. Л. Соболева

На правах рукописи УДК 519.1

МОГИЛЬНЫХ Иван Юрьевич

СОВЕРШЕННЫЕ 2-РАСКРАСКИ ГРАФОВ ДЖОНСОНА

Специальность 01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск, 2010

1 О ИЮН 2010

004603788

Работа выполнена в Институте математики им. С. Л. Соболева СО РАН

Научный руководитель: кандидат физико-математических наук,

C.B. Августинович. Официальные оппоненты: кандидат физико-математических наук,

В. А. Аксенов,

доктор физико-математических наук, профессор В. А. Зиновьев. Ведущая организация: Московский Государственный Университет

Защита состоится на заседании дис-

сертационного совета Д 003.015.01 при Институте математики им. С. Л. Соболева СО РАН по адресу: ауд. 417, пр. Академика Коп-тюга. 4, г. Новосибирск 630090.

С диссертацией можно ознакомиться в библиотеке Института математики им. С. Л. Соболева СО РАН.

Автореферат разослан " { fy " мая 2010 г.

Ученый секретарь диссертационного совета,

д.ф.-м.н. Î//7/J КХ Шамардин

-С'

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Под совершенной раскраской в т цветов (совершенной т-раскраской) графа G с матрицей А - понимается

раскраска вершин графа G в множество цветов {1,...,т} такая, что число вершин цвета j, смежных с фиксированной вершиной цвета, г, однозначно определено цветом последней вершины и равно a-ij. Матрица А называется матрицей параметров совершенной раскраски. Разбиение вершин графа G по цвету, естественно ассоциируемое с совершенной раскраской этого графа, в англоязычной литературе обычно называется equitable partition. Если такое разбиение получено дистанционным образом относительно некоторой совокупности С вершин графа, то множество С называют полностью регулярным кодом в графе G (по Ньюмайеру [27]). Отметим, что такое определение полностью регулярного кода совпадает с исходным, введенным Ф. Дельсартом в [11], если граф G является дистанционно-регулярным. Непосредственно из приведенных определений следует, что совершенные 2-раскраски есть суть полностью регулярные (в том числе и 1-совершенные) коды по Ньюмайеру с радиусом покрытия 1. В случае совершенных раскрасок в два цвета цвет номер 1 будем называть белым, а цвет номер 2 -черным.

Граф Джонсона J(n,w) (названный так в честь первого из исследователей одноименной ассоциативной схемы [22]) определяется как граф, вершинами которого являются всевозможные двоичные векторы длины new единичными координатами, пара векторов соединяется ребром, если они различаются ровно в двух координатах.

Одной из основных проблем теории кодирования и дискретной математики является проблема существования объектов с определенными свойствами. Вопросы существования таких структур как

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

Первая бесконечная серия совершенных блоковых кодов была построена Р. Хэммингом в 1950 году [19]. Спустя более чем 20 лет В. А. Зиновьев и В. К. Леонтьев [4], [5], и независимо Э. Титвайнен в [33], доказали что кодов с параметрами, отличными от параметров кода Хэмминга, за исключением двоичного и троичного кодов Голея над полями Галуа не существует.

Ф. Дельсарт в |11) ввел понятие полностью регулярных кодов в дистанционно-регулярных графах, класса кодов, включающего в себя совершенные коды и обладающих многими схожими с ними свойствами. Проблема существования полностью регулярных кодов в п-кубе является нерешенной, то есть известны не все параметры, для которых существуют полностью регулярные коды. Известно, что класс полностью регулярных кодов в п-кубе содержит равномерно упакованные коды в узком смысле, введенные Н. В. Семаковым, В. А. Зиновьевым и Г. В. Зайцевым в [б]. Этн коды включают совершенные и укороченные совершенные коды, выколотые коды Препараты, некоторые классы кодов БЧХ и выколотых кодов Рида-Маллера. Полное описание всех равномерно упакованных кодов было сделано X. К. А. ван Тилборгом в [34]. Упомянутая выше связь совершенных раскрасок и полностью регулярных кодов объясняет актуальность исследований равномерно упакованных кодов (в частности кодов Препараты) в рамках темы настоящей диссертации.

Проблема существования совершенных кодов в схеме Джонсона оказалась сложнее, чем аналогичная проблема в схеме Хэмминга. В работе [11], Дельсарт выдвинул гипотезу, что совершенных кодов в графе Джонсона не существует. Усилия целого ряда авторов так и не привели ни к ее доказательству, ни к ее опровержению. Один из лучших на сегодняшний день результатов был получен Д. Гордоном в 2006 году в работе [18]. Используя компьютер, он доказал, что не существует 1-совершенных кодов в графах Джонсона

J(n,w) при п < 2250.

Как отмечалось ранее, совершенные 2-раскраски являются обобщением 1-совершенных кодов. Заметим, что гипотеза Дельсарта. не может быть обобщена на совершенные 2-раскраски графов Джонсона. У. Мартин в работе [24] заметил, что совершенную 2-раскрас-ку J(n, ги) можно получить, покрасив блоки (и> — 1) — (и, ги, А)-схемы (при этом подразумевается что все блоки схемы различны) в один цвет, а оставшиеся вершины Л^п, и>) в другой цвет. Проблема существования таких схем при ю — 3 была решена М. Дегоном в 1983 в работе [10]; при ги = 4 для А = 1 (системы четверок Штейнера) X. Ханани в работе [20], для А = 2 А. Хартманом и К. Т. Фелпсом в [21], для А = 3 К. Т. Фелпсом, Д. Р. Стинсоном и С. А. Ван-стоуном в работе [28], для А = 0(тос1 3), где А=НОД(г> — 3,12)) доказана Л. Теирлинком в [31], для всех А, если п — 5 ■ 2т Т. Этци-оном и А. Хартманом в [12]. Проблема существования таких схем при ги = 4 и А отличных от вышеперечисленных, за исключением нескольких спорадических случаев, является открытой. Для ги = 4, 3-(25,4,4)-схема является схемой с наименьшим п, для которой вопрос существования открыт. Еще меньше результатов известно для ги > 5. При А = 1 получено несколько спорадических примеров для ю = 5,6 и не найдено ни одной такой схемы для и/ > 7. При А > 1 и го > 5 можно особо выделить работу Л. Теирлинка ]32], в которой установлено, что для любого го существуют (ги — 1) — (п, и>, А)-схемы при всех п = -ш — 1(тос/А), где А = (и»)!21""1.

В данной диссертации впервые предпринято систематическое исследование проблемы существования совершенных 2-раскрасок графов Джонсона, включающей в себя вопросы существования (ги— 1) — (п, и>, А)-схем и совершенных равновесных кодов.

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

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

Научная новизна.

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

1. Получен ряд конструкций совершенных 2-раскрасок графов Джонсона J(2w,w), 3{2/г,3) для произвольных го, к, а также найдены спорадические конструкции совершенных 2-раскрасок графов </(6,3), 7(8,3), 7(8,4). Найдены параметры всех выше перечисленных совершенных раскрасок.

2. Из работы А. Ньюмайера [27] следует, что число вершин белого цвета совершенной 2-раскраски дистанционно-регулярного графа, находящихся на расстоянии г от вершины х, зависит только от цвета вершины х и параметров совершенной раскраски. В диссертации получено обобщение этого результата - доказано, что количество вершин белого цвета совершенной 2-раскраскн дистанционно-регулярного графа, находящихся на расстоянии г от произвольного полностью регулярного кода С, определяется однозначно массивом пересечений кода. С, количеством белых вершин в С и параметрами совершенной 2-раскраски. Для доказательства использовалась система линейных алгебраических уравнений, схожая с системой уравнений, возникшей в работе Г. С. Шапиро и Г. Л. Злотника [30] при доказательстве дистанционной инвариантности совершенных кодов. Найденные в диссертации массивы пересечений некоторых полностью регулярных кодов в графах Джонсона позволили использовать данный результат для решения вопросов существования совершенных 2-раскрасок графов Джонсона.

Доказано, что совокупность белых вершин совершенной 2-раскраски графа J(n,w) является £ - (п,-ш, А)-схемой, найдены явные выражения для параметров t и А. Полученное свойство является обобщением свойства ¿-регулярности совершенных равновесных кодов, установленного Т. Этционом и М. Шварцем в [13]. Оно позволило использовать необходимые условия существования ¿-схем для решения вопросов существования совершенных 2-раскрасок графов Джонсона.

Анализируя графы, индуцированные сферами радиуса 1 и 2 в

графах Джонсона, получена нижняя оценка параметра а2\ совершенной 2-раскраски графа Джонсона с матрицей параметров Л2х2, доказано несуществование ряда совершенных 2-раскрасок графов Джонсона J(ll,3), J(12,5), J(13,4), J(9,3).

3. С помощью полученных конструкций и разработанных необходимых условий существования перечислены (теоретически, без использования компьютера) параметры всех совершенных 2-раскрасок графов Джонсона J(n, w) для п < 8. С помощью компьютера доказано несуществование ряда совершенных раскрасок некоторых графов Джонсона J(n, w) для п, больших 8.

4. В данной диссертации доказано, что всякая слабая изомет-рпя двух выколотых кодов Препараты является изометрией. С учетом установленной С. В. Августиновичем и Ф. И. Соловьевой в [2) метрической жесткости выколотых кодов Препарата отсюда вытекает, что слабоизометричные выколотые коды Препараты длины п > 210 - 1 являются эквивалентными, а группа автоморфизмов любого такого кода изоморфна группе автоморфизмов его графа минимальных расстояний. Аналогичные результаты доказаны для кодов Препараты длины, не меньшей 212.

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

Апробация работы. Результаты работы прошли апробацию на следующих международных конференциях: на конференции по алгебраической и комбинаторной теории кодирования АССТ-Х (Звенигород, 2006): на международных симпозиумах по проблемам избыточности в информационных системах PR.ICS XI (Санкт-Петербург, 2007 г.) и PRICS XII (Санкт-Петербург, 2009 г.); Втором международном симпозиуме по проблемам теории кодирования и приложениям, 2ICMCTA (Медина дель Кампо, Испания, 2008 г.); Международной конференции по совершенным кодам и смежным вопросам, (Стокгольм, Швеция, 2009 г.). Результаты диссертации

докладывались на семинаре "Теория кодирования" и семинара лаборатории "Теория Графов" НГУ и Института математики СО РАН. Кроме того, некоторые результаты диссертации докладывались на семинаре группы "Отдела инженерии, информатики и связи" Независимого Университета г. Барселоны, Испания, и на семинаре Дискретного отдела Королевского Технологического Института г. Стокгольма, Швеция.

Результаты диссертации отмечены дипломами Международной Студенческой Научной Конференции (МНСК-2006, МНСК-2007), грантом "Академическая мобильность" фонда Культурных Инициатив Михаила Прохорова в 2009 году, стипендией Сибирского Математического Журнала для аспирантов в 2010 году.

Основные результаты диссертации.

1. Получен ряд (как бесконечных, так и спорадических) конструкций совершенных 2-раскрасок графов Джонсона.

2. Установлены следующие свойства совершенных 2-раскрасок:

2.1. Доказано, что спектр множества белых вершин совершенной 2-раскраски графа G относительно полностью регулярного кода С однозначно определяется количеством белых вершин, принадлежащих множеству С, массивом пересечений полностью регулярного кода С и параметрами рассматриваемой совершенной 2-раскраски.

2.2. Доказано, что множество вершин фиксированного цвета всякой совершенной 2-раскраски графа J(n,w) с матрицей параметров А образует t — (п, и>, Л)-схему, где t и Л однозначно определяются числами n,w и матрицей А.

2.3. Получена нижняя оценка параметра а2\ совершенной 2-раскраски графа Джонсона с матрицей параметров А.

3. Перечислены параметры совершенных 2-раскрасок графов Джонсона J(n,w) для п < 8.

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

На защиту выносятся новые конструкции совершенных 2-раскрасок графов Джонсона, необходимые условия существования совершенных 2-раскрасок графов Джонсона.

Объем и структура диссертации. Диссертация состоит из введения, четырех глав, приложения и списка литературы (61 наименование). Объем диссертации 105 страниц, включая 14 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы диссертации, описывается взаимосвязь между различными комбинаторными объектами (полностью регулярными, в том числе и совершенными, кодами, блок-схемами) и совершенными раскрасками, приводится краткий обзор результатов о совершенных раскрасках различных графов и других близких к ним структур.

В первой главе приводится описание орбитного метода - классического способа построения таких комбинаторных объектов, как блок-схемы, совершенные раскраски различных графов. Используя орбитный метод, в этой главе получена серия как бесконечных, так и спорадических конструкций совершенных 2-раскрасок графов Джонсона, найдены параметры этих раскрасок.

Приведем основные определения и утверждения, касающиеся орбитного метода.

Автоморфизмом произвольного графа G называется подстановка на множестве вершин графа, сохраняющая отношение инцидентности между вершинами. Совокупность таких преобразова.-ний относительно операции суперпозиции образует группу, обозначаемую Aiit(G). Очевидно, что такая группа является подгруппой симметрической группы Sv> где v - число вершин графа G.

Пусть Н является некоторой подгруппой группы автоморфизмов графа G. Действие группы Н разбивает множество вершин графа, G на непересекающиеся орбиты. Поставив орбитам в соответствие различные цвета, получим орбитную раскраску вершин графа G, соответствующую подгруппе Н группы автоморфизмов графа G. Имеет место следующая

Теорема 1. [9j Всякая орбитная раскраска графа G является совершенной раскраской.

В общем случае число цветов в орбитной раскраске может оказаться достаточно большим. В отдельных случаях число цветов в этой раскраске можно уменьшить.

Лемма 1. (Об объединении цветов) [7J Пусть существует совершенная раскраска графа Gem цветов с матрицей параметров Лт.хт- Раскраска, получаемая из исходной объединением цветов в г групп Li,...,Lr: LiC\Lj = 0, Ц=1,...)Г ^ = {1,..., ттг} будет совершенной тогда и только тогда, когда выполнено условие: для любых i, j <Е {1,..., т}, i Ф j и любых p,s £ Li выполняется

У, арч= asi'

q€Lj

Под орбитным методом в данной диссертации понимается метод построения совершенных 2-раскрасок г>-вершинного графа, при котором множество вершин фиксированного цвета получается объединением некоторых орбит под действием некоторой подгруппы группы Sv.

В параграфе 1.1 получена следующая орбитная раскраска:

Теорема 2. Существует совершенная 3-раскраска графа Джонсона J(2m,3) со следующей матрицей параметров:

3(т - 3) 3(ш — 2) 6 \

т-2 5 (то - 3) +2 6

т — 2 3(т — 2) 2m - 1 J

Матрица порядка 3 из предыдущей теоремы обладает следующим интересным свойством: в каждом столбце два внедиагональных элемента равны, что позволяет с помощью Леммы 1 объединять любую пару цветов в один с сохранением свойства раскраски быть совершенной.

Следствие 1. Существуют совершенные 2-раскраски графа Джонсона J(2m,3), для т > 3 со следующими матрицами параметров:

( 3(2т - 5) 6 А / 3(то - 3) 3т \ \ Цт~ 2) 2т-1 )'\ т-2 5т - 7 ) и

/ 3(т - 1) 3(m - 2) \ { (m + 4) 5m -13 J '

Отметим, что совершенные 2-раскраски J(2т, 3) с первыми двумя матрицами параметров были найдены без использования леммы об объединении цветов К. Годсилом и Ч. Праэгер в [16].

Также объединением цветов получена следующая бесконечная серия совершенных раскрасок.

Теорема 3. Существуют совершенные 2-раскраски графа J(2w, w) для произвольного w,w > 3 со следующими матрицами параметров:

( w(w-2) 2w \ (w(w-1)+2 w-2 \ ^ 2(ш - 1) (го - I)2 + 1 J U ^ Зго w(w - 3) ) '

Перечислены все совершенные 2-раскраски графов Джонсона J(n, 2):

Предложение 1. Матрица любой совершенной раскраски J(n, 2) имеет вид

( 2(п _ 3) 2 или ( 2(п - Q _ 2) 2q ^ ^ п-2 п-2 ) ujl \ 2 (п - 1 - а) 2(а - 1) ) '

ade 0 < а < п — 2, при п четном, и о = 2,'4,..., п — 2, при п нечетном.

Рассмотрим полностью регулярный код (но Ныомайеру) С в графе G. Совокупность вершин на расстоянии j от кода С обозначим через Lj(C) и будем называть слоем дистанционного расслоения относительно С. Очевидно, что вершины графа G разбиваются на непересекающиеся слои Lj(C), j = 0,... ,р(С). Здесь под р(С) понимается радиус покрытия кода С - максимальное возможное расстояние от кода С до некоторой вершины графа G. Обозначим через d~,dj и dчисло вершин из слоев Lj-i(C), Lj(C) и Lj+\(C) соответственно, смежных с фиксированной вершиной х из слоя Lj(C). Согласно определению полностью регулярного кода, эти числа не зависят от выбора вершины х с j-го слоя. Набор чисел d~ ,($■, dt. j = 0, ...,р(С) называется массивом пересечения полностью регулярного кода С.

Пусть х является вектором веса г из Еп. Совокупность векторов у из Еп веса и>,ги > таких что для любого г € {1,..., п] выполнено г/г > хг будем называть шапкой (соответствующей вектору х). Слои дистанционного расслоения относительно таких кодов будем для краткости обозначать

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

Теорема 4. Шапка относительно вершины х веса г,г < ш является полностью регулярным кодом, при этом имеют место равенства: \Ь^(х)\ = С™~{+3С1, = (г - ]){п - ш - ¿), сЦ = (г - з)з + (ги - г + з)(п -ю- з), ^ = з{ти - г + з), где 0 < j < г.

Часть результатов первой главы получена совместно с С. В. Ав-густиновичем, эти результаты опубликованы в работах [37], [42], часть без соавторов, опубликованы в [36].

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

В параграфе 2.1 получена система линейных соотношений, связывающих спектр белого цвета некоторой совершенной 2-раскраски относительно полностью регулярного кода. Из этой системы следует, что спектр белого цвета некоторой совершенной 2-раскраски относительно полностью регулярного кода однозначно определяется параметрами совершенной раскраски, массивом пересечений полностью регулярного кода и количеством белых вершин в полностью регулярном коде.

Пусть С является неориентированным графом. Рассмотрим полностью регулярный код С в графе С и некоторую совершенную 2-раскраску графа С с множеством белых вершин IV. Упорядоченный набор чисел Ц(С) = \Ь^{С) П \¥\, з = 0,. . .,р(С) назовем спектром множества белых вершин совершенной раскраски относительно полностью регулярного кода С.

Приведенное выше определение полностью регулярного кода по Ньюмайеру эквивалентно исходному определению полностью регулярного кода, введенному Ф. Дельсартом в [11], если С* является

дистанционно-регулярным графом. Код С называется полностью регулярным (по Дельсарту) в графе (7, если количество кодовых вершин С, находящихся на расстоянии i от фиксированной вершины V, зависит только от расстояния от вершины V до кода С. Учитывая эквивалентность этих двух определений полностью регулярного кода, а также принимая во внимание, что множество вершин фиксированного цвета совершенной 2-раскраски является полностью регулярным кодом с радиусом покрытия 1, имеем

Предложение 2. [2 7] Пусть в - дистанционно регулярный граф. Тогда спектр множества белых вершин совершенной 2-раскраски графа б относительно вершины х не зависит от выбора вершины х, а зависит только от ее цвета и параметров совершенной раскраски.

В параграфе 2.1 обобщается приведенное утверждение, а именно доказывается, что спектр множества белых вершин совершенной 2-раскраскн графа (? относительно произвольного полностью регулярного кода однозначно определяется массивом пересечений этого кода, количеством белых вершин в самом коде и матрицей параметров этого кода.

Теорема 5. Пусть существует совершенная раскраска графа С в два цвета с матрицей А = и полностью регулярный (в

смысле Ньюмайера /21¡) код С с массивом пересечений О < з < р{С). Тогда имеют место соотношения:

Ь-ЛС^ + 1^С)(а21 - ап + <#) + 1т(С)д-+1 = \Ь,(С)\а.п, О <3<Р(С).

Таким образом, оказывается, что значения спектра связаны между собой системой линейных алгебраических уравнений с трех-днагоналыюй матрицей, задаваемой массивом пересечений кода С и параметрами совершенной 2-раскраски. Данное свойство является обобщением свойства дистанционной инвариантности 1-совер-шенных кодов в п-кубе, установленного Г. С. Шапиро и Г. Л. Злот-ником в [30]. С другой стороны, доказанное свойство является обобщением результата А. Ю. Васильевой |3] о спектре 1-совершенного

кода 7г-куба. в дистанционном расслоении относительно полностью регулярного кода. С учетом Теоремы 4 имеем следующее утверждение для совершенных 2-раскрасок графов Джонсона:

Следствие 2. Пусть существует совершенная 2-раскраска графа J(n, w), х - произвольная вершина веса г. Тогда для всех 0 < j < г выполняется

Ij-iWd+^+IjizXazi - au+$)+lm(x)dJ+1 = С{С^+3а2Ъ

где d+ = (г - j){n -ui-j),

= (i ~ j)j + (w-i+ j)(n -w- j), d~ = w(n - w) - d° - dj.

Следствие 2 можно рассматривать как необходимое условие существования совершенной 2-раскраски с заданной матрицей А порядка 2. Это позволило использовать компьютер для решения вопросов существования совершенных 2-раскрасок графов Джонсона с заданной матрицей параметров и с его помощью доказать несуществование ряда совершенных 2-раскрасок графов Джонсона J(n,w) для п, больших 8.

В параграфе 2.2 выявлена тесная взаимосвязь совершенных 2-раскрасок графов Джонсона и t-схем. А именно, доказано, что совокупность белых вершин совершенной 2-раскра.ски графа Джонсона является схемой силы t, найдено явное значение для t.

Раздел 2.2.1 носит вспомогательный характер. В нем приводятся необходимые определения и некоторые результаты К. Годсила и Г. Ройла |15J, Д. Цветковича, М. Дуба и X. Захса [9], касающиеся связи собственных значений графов и собственных значений совершенных раскрасок, описание пространств собственных векторов графа Джонсона в терминах книги [17]. Эти результаты используются в разделе 2.2.2., где доказывается основной результат параграфа 2.2. Приведем необходимые определения. Пусть G является произвольным неориентированным графом. Матрицей смежности графа G называется матрица М из нулей и единиц, строки и столбцы которой занумерованы вершинами графа G, элемент Мху, стоящий на пересечении строки, отвечающей вершине х и столбца, отвечающего вершине у, равен единице в том и только том случае,

когда (х, у) является ребром графа G. Далее под собственными значениями и собственными векторами графа G будем понимать собственные значения и собственные векторы матрицы смежности этого графа.

Рассмотрим совершенную раскраску графа G в произвольное число цветов. Собственным значением и собственным вектором совершенной раскраски с матрицей параметров Атхт графа G назовем собственные значения и собственный вектор матрицы Атхт. Связь между собственными значениями графа и совершенной раскраски этого графа дает следующее

Предложение 3. /9} Всякое собственное значение совершенной раскраски графа G является собственным значением G.

Рассмотрим граф Джонсона. J(n, w). Собственные значения этого графа были найдены Дельсартом при исследовании схем отношений Джонсона.:

Теорема 6. [llj Собственные значения графа Джонсона J(n,w) исчерпываются следующими числами: (w — j)(ii — го — j) — j, где О < j < w.

Собственное значение, равное (w — j)(n — w — j) - j, будем далее называть j-м собственным значением графа J(n,w).

В разделе 2.2.2 доказывается следующее вспомогательное

Предложение 4 Пусть существует совершенная 2-раскраска регулярного связного графа G степени t с матрицей параметров А = {a¿j}jj=i,2- Тогда оба числа ац — и t являются собственными значениями совершенной раскраски и собственными значениями графа G, причем ац — a2i не равно t.

С учетом этого утверждения далее младшим собственным значением совершенной 2-раскраски регулярного графа, будем называть собственное значение ац — агь отличное от валентности этого графа.

Рассмотрим совершенную 2-раскраску графа. Джонсона, с матрицей А. Через к обозначим число

п - 1 - у/(п -2w + I)2 + 4(и> + ац - а21)

2

Очевидно, что к зависит от п, и) и матрицы параметров рассматриваемой совершенной 2-раскраски, но для краткости далее их будем опускать. Основным результатом параграфа 2.2 является

Теорема 7. Пусть Ш является множеством белых вершин совершенной 2-раскраски графа с матрицей параметров А = 1,2- Тогда

1. младшее собственное значение ац — <221 равно собственному значению графа J(n,w) с номером к + 1, к > 0;

2. множество белых вершин этой совершенной раскраски IV является к — (п.ад, —^—С1и~ь )-схемой;

* 1 1 <112+021 П — к ' '

3. множество И7 не является (к + 1) — (п, и/, \)-схемой.

Это свойство позволяет использовать необходимые условия существования ¿-схем для получения следующих необходимых условий существования совершенной 2-раскраски 7(п,ш) с заданной матрицей параметров.

Следствие 3. Пусть существует совершенная 2-раскраска графа Т(п,ш) с матрицей параметров А = {«¿Л».7=1,2» число ац — <7.21 является (к + 1 )-м собственным значением графа Т(п,ъи). Тогда число —Щ1— ■ является целым для любого г. где 0 < г < к.

У. Мартин в [24] отметил, что (и> — 1) — (п,ш, А)-схема индуцирует полностью регулярный код с радиусом покрытия 1. То есть из (и> — 1) — (н. V), А)-схемы можно получить совершенную 2-раскраску, покрасив все векторы схемы в белый цвет, а векторы, не принадлежащие схеме - в черный. При этом младшее собственное значение полученной совершенной 2-раскраски равно —и>.

Отсюда, принимая во внимание Теорему 7, получаем, что других совершенных раскрасок с младшим собственным значением, равным —ш, не существует:

Следствие 4 Совершенная 2-раскраска Т(п, и>) с матрицей параметров А = {ог3}г,7=1,2, с собственным значением, равным —и>, существует тогда и только тогда, когда существует (ги — 1) — (п, го, —Щ1—(п — ш + \))-схема.

В параграфе 2.3, используя тот факт, что подграф, индуцированный сферой радиуса 1 в графе Джонсона, изоморфен декартовому произведению двух полных графов, показывается, что параметр a2i совершенной 2-раскраски графа. Джонсона оценивается снизу функцией от ii,w,a\2. Доказательство этой теоремы сводится к нахождению решения некоторой дискретной экстремальной задачи.

Пусть b - некоторое целое число от 0 до w(n — w). Введем обозначение s(b) = r^jl-

Теорема 8. Пусть существует совершенная 2-раскраска графа J(ii,w) с матрицей А = {aij}ij-it2 такой, что и> < + 2.

Тогда а.21 > п - з(а12) + 1 - Li&l •

Применяя Теорему 8, удалось доказать несуществование некоторых совершенных 2-ра.скрасок для п < 12. Отметим, что эти раскраски удовлетворяют описанным выше необходимым условиям существования совершенных раскрасок, то есть Следствиям 2 и 3.

Следствие 5. Не существует совершенных раскрасок графов J(10,5), .7(12,4), ,7(12,5), .7(12,6) с матрицами параметров

/9 1б\ /12 20\ /15 20\ /16 20\ \2 23у ' у 2 30j ' \ 2 33 J ' \ 2 34J

соответственно.

В параграфе 2.4 приведено дальнейшее развитие идей, изложенных в параграфе 2.3.

Для решения вопросов существования совершенных 2-ра.скрасок в параграфе 2.4 проводится анализ структуры части совершенной раскраски графа. Джонсона, на подграфе, индуцированном вершинами сферы радиуса 2. Отметим, что впервые аналогичный подход для решения вопросов существования совершенных 2-раскраеок (метод "локальных аргументов") был применен Д. Г. Фон-дер-Флаассом в [8] для доказательства необходимых условий существования совершенных раскрасок в два цвета графа. п- мерного куба Еп.

С использованием описанной выше идеи доказывается несуществование некоторых совершенных 2-раскрасок графов Джонсона с небольшими значениями параметра 021, удовлетворяющих необходимым условиям существования совершенных 2-раскрасок, описанным в Следствиях 2, 3 и Теореме 8.

Теорема 9. Не существуют совершенные 2-раскраски графов 7(11,3), «7(12,5), 7(13,4), 7(9,3) с матрицами

соответственно. Кроме того, не существует совершенных рас-

Результаты второй главы опубликованы в работах [35], [36|, (41|.

В третьей главе перечислены параметры всех совершенных 2-раскрасок графов 7(6,3), 7(7,3), 7(8,3) и 7(8,4).

Отметим различие задач перечисления параметров совершенных 2-раскрасок графов Джонсона и перечисления совершенных 2-раскрасок этих графов. Так как класс совершенных 2-раскрасок графов Джонсона включает в себя, помимо множества различных комбинаторных объектов различной структуры, системы троек Штейнера, то задача перечисления совершенных раскрасок не легче задачи перечисления систем троек Штейнера. Последняя задача далека от своего решения - лучшим на сегодняшний день является результат [23] П. Р. Д. Остергарда и П. Каски, перечисливших все неизоморфные системы троек Штейнера порядка 19, которых оказалось 11084874829. В данной диссертации задача перечисления всех неизоморфных совершенных 2-раскрасок графов Джонсона не рассматривается.

В параграфе 3.1 доказаны некоторые утверждения, касающиеся совершенных 2-раскрасок антиподальных графов. В частности, из Утверждения 2 следует, что пары вершин таких графов, находящиеся на максимальном расстоянии, распадаются либо на пары, окрашенные в разные цвета (в таком случае раскраска именуется минус-антиподалъной), либо на пары, окрашенные в один

6 12 4 14

красок графа 7(12,4) с матрицами

цвет (в таком случае раскраска называется плюс-антиподальнои). С использованием установленных свойств антиподальных раскрасок в параграфе 2.1 перечислены параметры всех совершенных 2-раскрасок графа Джонсона J(6,3):

Теорема 10 Матрицы параметров совершенных 2-раскрасок графа 7(6,3) исчерпываются следующим списком:

0 9 \ / 1 8 \ / 2 7 А / 3 6 \ /45

1 8 )' 2 7 Г I 3 6 Г 14 5/' 5 4

3 6 \ /63 6 3 / ' I 3 6

(1)

(2)

Причем любая совершенная раскраска с матрицей из списка (\) является плюс-антиподальнои, а из списка (2) - минус-антиподаль-ной.

Основным результатом параграфа 3.2 является следующая

Теорема 11 Матрицы параметров совершенных раскрасок 7(7, 3) в два цвета исчерпываются следующим списком:

4 8)' <3>

О 12 Л / 3 9 Л

з э;и (б б ] •

В параграфах 3.3 и 3.4 перечислены параметры совершенных 2-раскрасок графов 7(8,3) и 7(8,4) соответственно. Для доказательства (в дополнение к совершенным 2-раскраскам, описанным в главе 1) построено две спорадические (т.е. такие, которые нельзя обобщить на бесконечные число графов Джонсона) совершенные 2-раскраски этих графов. Это совершенная раскраска Л(8,3) с

„ / 5 10 Л Т/.

матрицей I ^ Ц / 11 совеРшенная раскраска 7(8,4) с матрицей

/6 ю Л

V 4 12 /

Теорема 12. Матрицы параметров совершенных 2-раскрасок графа 7(8,3) исчерпываются следующим списком:

(12 3\/3 12\/5 10\ / 7 8 \ \ 5 10 У ' V 2 13 / ' \ 4 11 ^ " \ 6 9 )■

Теорема 13. Матрицы параметров совершенных 2-раскрасок графа 7(8,4) исчерпываются следующим списком:

(12 4 \ (б 10 Л (А 12 Л /8 8 \ 1^4 12 )\а 12 у! ' 2 14 у ' \ 6 10 У'

/0 16 Л /4 12 \ ^4 12 У " V 8 8 )•

Результаты третьей главы получены совместно с С. В. Августи-новичем и опубликованы в [38], [42].

В четвертой главе исследовались слабые изометрии выколотых кодов Препараты. Приведем несколько дополнительных определений.

Код С будем называть приведенным, если он содержит нулевой вектор. Два кода С\ и С2 длины п называются эквивалентными, если существует автоморфизм Р пространства Еп, такой что Г(С1) = С2. Отображение 1 \ С\ Сг двух кодов С\ и С2 называется изометрией (а коды Сх и С2 изометричными), если д(х,у) = й(1(х),1(у)) выполнено для всех х и у из С\. Отображение 3 : С\ С2 называется слабой изометрией кодов С\ и С2 (а коды С\ и С2 слабо изометричными), если для всех х,у из С\ равенство <1(х,у) = й имеет место тогда и только тогда, когда й(3(х),3(у)) — й, где й - кодовое расстояние кода С\. Граф минимальных расстояний кода С определяется как граф, множество вершин которого совпадает с множеством кодовых слов кода С; пару вершин х, у полагают смежными при ¿(х, у) = с1, где с1 - кодовое расстояние кода С. Кодом Препараты Рп называется двоичный код длины п = 2'п мощности 22"*~2т для четного т > А с кодовым расстоянием 6. Выколотый код Препараты (то есть код, полученный из кода Препараты удалением фиксированной координаты из всех кодовых слов) длины п = 2т - 1 будем обозначать через Рп. Коды

Препараты и выколотые коды Препараты обладают целым рядом полезных свойств. В работе [6] Н. В. Семаков, В. А. Зиновьев и Г. В. Зайцев ввели понятие равномерно упакованного (в узком смысле) кода, доказали что выколотый код Препараты является равномерно упакованным в узком смысле. В той же работе доказано, что множество вершин минимального веса приведенных (выколотых) кодов Препараты длины п образует 3 - (п, 6, (тг - 4)/3)-схему (2 — (п, 5, (п — 3)/3)-схему соответственно). Позднее, те же авторы |29]) доказали, что выколотый код Препараты однозначно достраивается до 1-совершенного кода.

С. В. Августинович установил в |1), что всякие два слабо изо-метрнчных 1-совершенных кода эквивалентны. В работе (25) доказано, что всякий расширенный 1-совершенный код восстанавливается с точностью до эквивалентности по своему графу минимальных расстояний. Как следствие, всякие два слабо изометричных расширенных 1-совершенных кода являются эквивалентными.

В параграфе 4.1 с помощью анализа структуры 2 — (п,5,.(п — 3)/3)-схемы, образованной кодовыми словами минимального веса приведенного выколотого кода Препараты длины п п модификацией подхода, предложенного в [1|, доказана следующая

Теорема 14. Пусть Т : Р" —» Р£ является слабой изометрисй двух выколотых кодов Препараты Р" и Рр длины п. Тогда Т является изолгетрией.

С учетом установленной С. В. Августиновичем и Ф. И. Соловьевой в [2\ метрической жесткости выколотых кодов Препарата из Теоремы 15 вытекает, что слабоизометричные выколотые коды Препараты длины п > 210 — 1 являются эквивалентными, а группа автоморфизмов таких кодов изоморфна группе автоморфизмов графа минимальных расстояний этих кодов.

Следствие 6. Пусть п > 210 — 1. Два выколотых кода Препараты длины п слабоизометричны тогда и только тогда, когда они эквивалентны.

Следствие 7. Группа автоморфизмов выколо7пого кода Пре71ара-ты длины п, и > 210 - 1 изоморфна группе автоморфизлюв графа минимальных ратпояний этого кода.

В параграфе 4.2, используя рассуждения, аналогичные рассуждениям из параграфа 4.1 доказаны следующие результаты:

Теорема 15. Пусть 3 : Р" —> Р£ является слабой изометрией двух кодов Препараты Р" и длины п. Тогда 7 является изометрией.

Следствие 8. Пусть п > 212. Два кода Препараты длины п являются слабоизометричными тогда и только тогда, когда они эквивалентны.

Следствие 9. Группа автоморфизмов кода Препараты длины п, п > 212 изоморфна группе автоморфизмов графа минимальных расстояний этого кода.

Актуальность полученного в Теореме 15 результата подтверждается публикацией К. Т. Фелпса. и К. Фернандес (14] (независимо полученной после представления автором диссертации статьи в журнал "Проблемы передачи информации"). В этой работе доказана однозначная восстановимость кода Препараты по графу его минимальных расстояний. Как следствие этого результата, два сла-боизометричных кода Препараты произвольной допустимой длины эквивалентны. В отличие от работы [14] в настоящей диссертации слабые изометрии исследованы как для выколотых кодов Препараты, так и для кодов Препараты.

Результаты четвертой главы опубликованы в работах [39], [40].

В Приложении приводятся результаты работы компьютерной программы, провер51ющей выполнение разработанных в диссертации необходимых условий существования совершенных 2-раскрасок графов Джонсона </(п,ги) при 9 < п < 12, см. Теоремы 8, 9 и Следствия 2 и 3.

Автор выражает глубокую искреннюю благодарность и признательность научному руководителю Сергею Владимировичу Авгу-стиновичу, а также Фаине Ивановне Соловьевой, которой принадлежит постановка задачи четвертой главы настоящей диссертации.

Список литературы

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

[2] Августинович С.В., Соловьева Ф.И. О метрической жесткости двоичных кодов // Пробл. передачи ннформ. 2003. Т. 39. N. 2. С. 63-68.

[3J Васильева А.Ю. Спектральные свойства совершенных двоичных (п,3)-кодов // Дискрет, анализ и исслед. операций. 1995. Т. 2. N. 2. С. 16-25.

[4] Зиновьев В. А., Леонтьев В.К. О совершенных кодах // (Пре-принт/ИППИ АН СССР). 1972. Вып. 1. С. 26-35.

[5J Зиновьев В. А., Леонтьев В.К. Несуществование совершенных кодов над полями Галуа // Проблемы управления и теории информации. 1973. Вып. 2. С. 123-132.

[6] Семаков Н.В., Зиновьев В.А., Зайцев Г.В. Равномерно упакованные коды // Пробл. передачи информ. 1971. Т. 7. N. 1. С. 38-50.

[7) Пузынина С. А. Периодичность совершенных раскрасок радиуса г>1 бесконечной прямоугольной решетки // Материалы VI молодежной научной школы по дискретной математике и ее приложениям (Москва, 16-21 апреля 2007 г.). Часть II. Под редакцией А. В. Чашкина. 2007. С. 29-35.

[8J Фон-дер- Флаасс Д.Г. Совершенные 2-раскра.ски гиперкуба // Спб. мат. журн. 2007. Т. 48. N. 4. С. 923-930.

[9j Цвегпкович Д., ДубМ., Захс. X. Спектры графов: теория и применение /'/ Киев, Наукова Думка. 1984. 384 с.

[10] Dehon М. On the existence of 2-designs S\(2,3,v) without repeated blocks // Discrete Math. 1983. V. 43. P. 155-171.

llj Delsarte P. An Algebraic Approach to the Association Schemes of Coding Theory // Philips Res. Rep. Suppl. 1973. V. 10. P. 1-97.

12] Etzion T., Hartman A. Towards a large set of Steiner quadruple systems // SIAM J.Discrete Math. 1991. V. 4, P. 182-195.

13] Etzion T., Schwarz M. Perfect Constant-Weight Codes // IEEE Trans. Inform. Theory. 2004. V. 50. N. 9. P. 2156-2165.

14] Fernandez-Cordoba C., Phelps K. T. On the minimum distance graph of an extended Preparata code // Designs, Codes and Cryptography submitted.

15] Godsil C., Royle G. Algebraic Graph Theory // Springer Science+Business Media. LLC. 2004.

16] Godsil C., Praeger C., Completely transitive designs, preprint.

17] Godsil C. Association schemes // Combinatorics and Optimization. University of Waterloo. 2005.

18] Gordon M.D. Perfect Single Error-Correcting Codes in the Johnson Scheme // IEEE Trans. Inform. Theory. 2006. V. 52. N. 10. P. 4670-4672.

19] Hamming R. W. Error detecting and errorcorrecting codes // Bell Syst.Tech.J. 1950. V. 29. P. 147-160.

20] Hanani H. On quadruple systems // Canad. J. Math. 1960. V. 15. P. 145-157.

21] Hartman A., Phelps K.T. Tetrahedral quadruple systems // Utilitas Math. 1990. V. 37. P. 181-189.

22] Johnson S. M. Upper bounds for constant weight error-correcting codes // Discr.Math. 1972. V. 3. P. 109-124.

23] P. Kaski, P. R. J. Ostergârd, The Steiner triple system of order 19 ,// Math. Comp. 2004. V. 73. P. 2075-2092.

24] Martin W. J. Completely Regular Designs //J. Combin. Designs. 1998. V. 6. N. *l. P. 201-273.

[25| Mogilnykh I.Yu., Ostergdrd P.R.J., Pottonen 0.. Solov'eva F.I. Reconstructing Extended Perfect Binary One-Error-Correcting Codes from Their Minimum Distance Graphs // IEEE Trans. Inform. Theory. 2009. V. 55. N. 6. P. 2622-2625.

[26] Meyerowitz A. Cycle-balanced partitions in distance-regular graphs // Discr.Math. 2003. V. 264. P. 149-165.

[27] Neumaier A. Completely regular codes // Discrete Mathematics 1992. V. 106/107. P. 353-360.

[28] Phelps K. T., Stinson D.R., Vanstone S.A. The existence of simple 63(3,4,1;) // Discrete Math. 1989. V. 77. P. 255-258.

[29] Semakov N.V., Zinoviev V.A., Zaitsev G.V. Interrelation of Preparata and Hamming codes and extension of Hamming codes to new double-error correcting codes // Proc.2nd Intern. Sympos. Information Theory. Tsakhadsor, Armenia, 1971. Budapest: Akad.Kiado, 1973. P. 257-263.

[30] Shapiro G. S., Slotnik D. S. On the mathematical theory of error correcting codes // IBM Journal of Research Development. 1959. V. 3. P. 68-72.

|31) Teirlinck L. On large sets of disjoint quadruple systems // Ars Combinatoria. 1984. V. 17. P. 173-176.

[32] Teirlinck L. Non-trivial t-designs without repeated blocks exist for all t, a Discr. Math. 1987. V. 65. Lss. 3. P. 301-311.

[33] Tietavainen A. On the nonexistence of perfect codes over the finite fields 11 SIAM J.Appl. Math. 1973. V. 24. P. 88-96.

[34] Van Tilborg H. C. A. Uniformly packed codes // Ph. D. Thesis, Eindhoven University of Technology, the Netherlands, 1975.

Публикации автора по теме диссертации

[35] Mogilnykh I. Yu. On k-regularity of perfect colorings of Johnson graphs in two colors // Proceedings of Tenth International workshop on Algebraic Combinatorial Coding Theory (ACCT-2006), P. 198-202. September 3-9 2006, Zvenigorocl, Russia.

[36] Могильных И.Ю. О регулярности совершенных раскрасок графа Джонсона в два цвета // Пробл. передачи ин-форм. 2007. Т. 43. N 4. С. 37-44.

[37] Mogilnykh I.Yu., Avgustinovich S.V. Perfect colorings of Johnson graph in two colors // Proceedings of XI International Symposium on Problems of Redundancy in Information and Control Systems (Saint-Peterburg, Russia, July 2-6, 2007). P. 205-209. '

[38] Avgustinovich S.V., Mogilnykh I.Yu. Perfect 2-colorings of Johnson graphs J(6,3) and .7(7,3) // LNCS, Springer, 2008. V. 5228. P. 11-19.

[39] Могильных И.Ю. О слабых изометриях кодов Препараты // Пробл. передачи информ. 2009. Т. 45. N. 2. С. 78-83.

[40] Mogilnykh I. Yu. Weak isometries of Preparata codes // Proceedings of XII International Symposium on Problems of Redundancy in Information and Control Systems (Saint-Peterburg, Russia, May 26-30, 2009). P. 96-100.

[41] Могильных И.Ю. О несуществовании некоторых совершенных 2-раскра.сок графов Джонсона // Дискрета, анализ и исслед. опер. 2009. Т. 16. N 5. С. 52-68.

[42] Августпинович С.В., Могильных И.Ю. Совершенные раскраски графов Джонсона J(8,3) и J(8,4) в два цвета// Дискретн. анализ и исслед. опер. 2010. Т. 17. N 2. С. 3-19.

Могильных Иван Юрьевич

Совершенные 2-раскраски графов Джонсона

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 06.05.2010г. Формат 60x84 1\16

Усл. печ. л. 1,75 Заказ № 88 Тираж 100 экз.

Отпечатано в типографии ООО « Омега Принт» 630090, г. Новосибирск, пр. Ак.Лаврентьева,6, оф.3-021 тел/факс ( 383) 335-65-23 email: omegap@yandex.ru

Введение

1 Конструкции совершенных 2-раскрасок графов Джонсона

2 Необходимые условия существования совершенных 2-раскрасок графов Джонсона

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

2.2 Пространства собственных векторов и свойство к-регулярности совершенных раскрасок.

2.2.1 Собственные значения и собственные векторы графов

2.2.2 Собственные значения совершенных 2-раскрасок графа Джонсона и свойство к-регулярности

2.3 Нижняя оценка параметра 0,21 совершенной 2-раскраски графа Джонсона.

2.4 Несуществование некоторых совершенных 2-раскрасок графов Джонсона.

3 Совершенные 2-раскраски графов Л(п,ш), п <

3.1 Совершенные 2-раскраски графа .1(6,3).

3.2 Совершенные 2-раскраски графа ,1(7,3).

3.3 Совершенные 2-раскраски графа <7(8,3).

3.4 Совершенные 2-раскраски графа Л(8,4).

4 Слабые изометрии кодов Препараты

4.1 Слабые изометрии выколотых кодов Препараты.

4.2 Слабые изометрии кодов Препараты.

В данной диссертации исследуется вопрос существования совершенных 2-раскрасок графов Джонсона. Под совершенной раскраской в т цветов (совершенной т-раскраской) графа С с матрицей А = («и К ,]=\,.,т понимается раскраска множества вершин графа С в множество цветов {1,. . . , т] такая, что число вершин цветам, смежных с фиксированной вершиной цвета г, не зависит от выбора последней вершины и равно Матрица А называется матрицей параметров совершенной раскраски. В случае т = 2, цвет под номером 1 будем называть белым, а цвет под номером 2 - черным; совокупность всех вершин белого цвета графа С? будем обозначать IV, черного - В. В случае двуцветной совершенной раскраски, параметр ац будем называть внутренней степенью г-го цвета, а параметр а^, j ф г будем называть внешней степенью г-го цвета.

Обозначим через Еп совокупность всех двоичных векторов длины п. Расстоянием Хэмминга между двумя векторами ж и у из Еп называют количество различных координат в векторах х и у. Граф Джонсона J(n, ги) (названный в честь первого из исследователей одноименной схе--мы ассоциативности [39]) определяется как граф, вершинами которого являются всевозможные вектора из Еп веса ги, пара векторов соединяется ребром, если они находятся на расстоянии 2 по Хэммингу. Наименьшее число ребер графа Джонсона в пути, соединяющем вершины хну называется расстоянием Джонсона. Отметим, что граф Л^п, ги) является изоморфным графу п — ги). Поэтому в настоящей диссертации рассматриваются только графы J(n,w) при w < п/2.

Укажем некоторые простейшие свойства графа Джонсона. Очевидно, что граф Джонсона J(n,w) является регулярным графом степени win — w). Более того, сфера радиуса 1 с центром в любой вершине этого графа изоморфна графу Kw х Kn-W (подробнее см. далее параграф 2.3). Также легко видеть, что диаметр графа J(n, w) (максимально возможное расстояние между парой вершин этого графа) равняется w. Граф Джонсона J(2w,w) является антиподальным, то есть его вершины однозначно разбиваются на пары, находящиеся на максимальном расстоянии друг от друга.

Напомним, что граф называется дистанционно-регулярнымесли количество вершин z, находящихся на расстоянии г, j от фиксированных вершин у их соответственно, удаленных друг от друга на расстоянии к, есть число, не зависящее от выбора х,у, а зависящее только от i,j,k. Граф Джонсона J(n, w) является дистанционно-регулярным графом для всех п и ги [24].

Введем несколько дополнительных определений. Рассмотрим граф G — (V,E). Шар радиуса i с центром в вершине v определяется как Bj(v) = {w £ V : dc(v,w) < г}, где dc{v,w) равно числу ребер в кратчайшем пути, соединяющим вершины v и w. Произвольное подмножество вершин V' множества V называется кодом в графе G. Подмножество вершин С множества V называется е-совершенным кодом в графе G, если шары радиуса е с центрами в вершинах из С образуют разбиение множества всех вершин графа G. В случае, когда совершенный код С совпадает со всем множеством V, т. е. е = 0 или состоит не более чем из двух вершин, С называют тривиальным совершенным кодом.

Обозначим через Е™ множество векторов пространства {(a?i,., хп) : Х{ G GF(q)}. Пару векторов этого пространства соединим ребром, если эти векторы различаются в одной координате. Таким образом, получим граф, называемый графом Хэмминга. Совершенный код в таком графе называют q-значным совершенным кодом. Согласно известной теореме В. А. Зиновьева и В.К. Леонтьева [7], [8], полученной независимо Э. Титвайненом в [54], нетривиальные совершенные коды над полем Галуа существуют только длины п = {дт — 1 )/(д — 1), где т - любое натуральное число, не меньшее двух, с кодовым расстоянием 3, длины п = 23 - двоичный код Голея с кодовым расстоянием 7, а также длины п = 11 - это троичный код Голея с кодовым расстоянием 5.

В отличии от графа Хэмминга, проблема существования совершенных кодов в графах Джонсона является нерешенной.

В [24] Ф. Дельсарт ввел понятие полностью регулярного кода, включающего в себя е-совершенные коды. Пусть С является кодом в графе С. Следующие множества будем далее именовать слоями дистанционного разбиения вершин графа О (относительно С)\ Ь${С) = С и = {у € V : £¿7(у, С) = при 0 < j < рс- Здесь через рс обозначен радиус покрытия кода - максимальное возможное расстояние от кода до вершин графа. Очевидно, что = ио<^<рсЬ^{С). Такое разбиение будем называть дистанционным разбиением мноэк-ества вершин графа С относительно множества С. Разбиение относительно С называется дистанционно-регулярным, если число вершин из слоев с номерами ] — 1, и ^ + 1 (эти числа в дальнейшем будем обозначать (1^, Щ и д^), смежных с каждой вершиной из ^'-го слоя не зависит от выбора последней. Код С, обладающий таким свойством, называется полностью регулярным (по Ньюмайеру [44]), а набор чисел а^, с^, где 0 < j < р(С) - массивом пересечений полностью регулярного кода С.

Рассмотрим раскраску вершин графа С, при которой все слои дистанционного разбиения относительно С красятся в разные цвета. Такую раскраску назовем дистанционной раскраской (индуцированной кодом С). Используя понятие дистанционной раскраски, полностью регулярный код можно определить как множество одноцветных вершин некоторой совершенной раскраски: С является полностью регулярным кодом тогда и только тогда, когда соответствующая ему дистанционная раскраска является совершенной.

Очевидно, что раскраска вершин графа в два цвета является совершенной тогда и только тогда, когда множество вершин фиксированного цвета такой раскраски является полностью регулярным кодом с радиусом покрытия 1. Таким образом, проблема существования совершенных т-раскрасок ■при т = 2 эквивалентна проблеме существования полностью регулярных кодов с радиусом покрытия 1, и включает в себя проблему существования полностью регулярных кодов с радиусом покрытия 7П — 1 при т > 2.

Отметим, что приведенное определение полностью регулярного кода по Ньюмайеру [44] эквивалентно исходному определению полностью регулярного кода по Дельсарту [24], если код рассматривается в дистанционно-регулярном графе.

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

Класс полностью регулярных кодов в Еп содержит равномерно упакованные коды (в узком смысле), введенные Н.В. Семаковым, В.А. Зиновьевым и Г.В. Зайцевым в [12]. Пусть С является двоичным кодом в Еп с кодовым расстоянием с1. Обозначим через е число ошибок, исправляемых кодом С, е — — Обозначим через У совокупность векторов из Еп, которые находятся от кода С на расстоянии не меньшем е. Для всякого вектора у из У определим г (у) равным числу кодовых слов с из кода С, таких что е < < е + 1. Код С называется равномерно упакованным, если г (у) есть постоянная величина для любого у из У. Параметр г называется плотностью упаковки. В работе [12] установлено, что такие коды обладают важными свойствами, например, они являются полностью регулярными, а кодовые слова фиксированного веса таких кодов образуют блок-схемы. Там же перечислены все максимальные равномерно упакованные коды. Таковыми кодами оказались выколотые коды Препараты, совершенные коды и выколотые 1-совершенные коды. Полное описание всех равномерно упакованных кодов было сделано X. К. А. Ван Тилборгом в [53]. Оказалось, что эти коды исчерпываются кодами с максимальной плотностью упаковки, кодом Адамара с параметрами (11,24,5), кодами БЧХ с параметрами , п—4г—2, 5), выколотыми кодами Рида-Маллера с параметрами

22г-1 2г-1 Х) п 2г> 3)5 (22г-1 + -1,п- 2г, 3).

В 1992 А. Ныомайер [44] предположил, что, кроме расширенного кода Голея, не существует таких кодов с кодовым расстоянием, большим 7 (коды с большим кодовым расстоянием представляют особый практический интерес, так как позволяют исправлять много ошибок). В 2008 г. К. Боргесом, Ж. Рифой и В. А. Зиновьевым эта гипотеза была опровергнута в работе [21], в которой показано, что совокупность кодовых слов четного веса двоичного кода Голея является полностью регулярным кодом с кодовым расстоянием 8 и радиусом покрытия 8. В этой работе также перечислены все неантиподальные двоичные полностью регулярные коды с минимальным расстоянием 3. В работе [47] В.А. Зиновьевым и Ж. Рифой полностью описаны полностью регулярные коды в Е™ с радиусом покрытия 1 (т.е. коды, индуцирующие совершенные 2-раскраски), обладающие свойством линейности. Показано, что такие коды являются полностью транзитивными. В описании были использованы различные конструкции, например, конструкция, основанная на кронекеровом произведении проверочных матриц кодов. Ранее такой метод был предложен теми же авторами в [48].

Описанием совершенных 2-раскрасок п-мерного куба занимался Д. Г. Фон-дер-Флаасс. В работе [30] им получена граница корреляционной иммунности булевых функций, на ее основе установлено новое необходимое условие существования совершенной 2-раскраски п-мерного куба Еп с заданной матрицей параметров. Д. Г. Фон-дер-Флаасс исследовал в работе [14] совершенные 2-раскраски куба Е12, достигающие упомянутой выше границы корреляционной иммунности: построены новые такие раскраски, перечислены все их матрицы параметров. Некоторые конструкции совершенных раскрасок Еп и необходимые условия их существования получены в [13].

Рассмотрим 1-совершенный код в произвольном графе степени Ь. Покрасив в белый цвет кодовые вершины, а в черный цвет - некодовые, получим совершенную 2-раскраску с матрицей

Вопрос существования нетривиальных совершенных кодов в графе Джонсона имеет давнюю историю. В 1973 году Ф. Дельсарт выдвинул гипотезу о несуществовании нетривиальных совершенных кодов в графах Джонсона (также именуемых равновесными совершенными кодами) [24]. Среди тривиальных 1-совершеиных кодов в графах Джонсона существует только код в (/(6,3), состоящий из пары аптиподальных (на максимальном расстоянии друг от друга) вершин (подробнее см. конструкцию 6 раздела 3.1).

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

Один из первых результатов был получен Э. Баннаи [18], который показал, что не существует е-совершенных кодов в графе Джонсона J(2w+ 1,го) для е > 2. Этот результат был впоследствии улучшен П. Хэммон-дом в [36], который доказал, что не существует совершенных кодов в графах Джонсона J(2w + 1,го) и J(2w + 2, го).

Подмножество множества вершин графа (? диаметра И назовем И-антикодом. Антикод диаметра И называется оптимальным, если он имеет максимальную мощность среди всех кодов диаметра Рассмотрим такие два кода X и У в некотором дистанционно-регулярном графе с множеством вершин V, что ненулевые расстояния между вершинами из X не возникают как расстояния между вершинами из У. Ф. Дельсарт в [24] (см. Теорема 3.9) доказал, что |Х||У| < [У|. Используя этот результат и понятие оптимального антикода, К. Роос в [49] заметил, что если существует е-совершенный код, то е-сферы должны быть оптимальными антикодами диаметра 2е. Используя этот факт, он доказал, что необходимым условием существования е-совершенных кодов в графе является оценка п < (ги — 1)(2е+ 1)/е. Понятие антикода также использовалось в [16] для исследования вопроса существования диаметральных совершенных кодов (обобщения совершенных кодов).

Т. Этциоп является автором многих других работ, посвященных проблеме существования совершенных кодов в графах Джонсона. В работах [27], [28], [29] им доказано несуществование совершенных кодов в многих графах Джонсона, в частности в графах Л2т + р, и>), где р - произвольное простое число. Также им установлены и изучены такие различные свойства совершенных равновесных кодов, как наличие структур, изоморфных системам Штейнера, вложенных в совершенные коды, свойство /с-регулярности совершенных кодов и другие свойства. Остановимся подробнее на свойстве ^-регулярности.

В [27] Т. Этционом и М. Шварцем было введено следующее определение: совершенный код С называется к-регулярным, если выполнены два условия:

1) Существуют целые числа . такие, что для любого подмножества А мощности к, содержащегося в множестве {1,. ,п}, выполняется: \{с Е С : |зирр(с) Г) А\ = г}| = щ для любого г из

2) Для любого подмножества А множества {1,. ,п}, \ А\ = к, существуют числа (За(0), ■ ■ •, /Зл(к) такие, что для любого подмножества I из множества А верно: |{с Е С : Бирр(с) П А — /}| = ¡За{\1\).

В [27] Т. Этционом и М. Шварцем найдено выражение через п,ги для максимального к, для которого код является /г-регулярным. Используя введенное свойство ^-регулярности, Т. Этцион и М. Шварц доказали, что не существует нетривиальных 1-совершенных кодов в графах Джонсона при п < 50000, а также нетривиальных 2-совершенных кодов в графах Джонсона при п < 40000. Также ими показано, что не существует 3-совершенных, 7-совершенных, 8-совершенных кодов в графах Джонсона. Введенное понятие /^-регулярности можно переформулировать в терминах классического объекта дискретной математики -блок-схемы. Напомним, что £ — (п, ги, А)-схемой называется такая совокупность ги-элементных подмножеств (именуемых блоками) фиксированного ?г-элементного множества, что всякое ¿-элементное подмножество встречается ровно в А блоках. В данной диссертации мы рассматриваем только схемы, все блоки которой различны. Такие схемы называют также простыми. Это условие позволяет рассматривать t — (п,ги, А)-схемы как совокупности некоторых вершин графа Джонсона J(n, ги). В работе [28] Т. Этцион заметил, что совершенный код является /с-регулярным тогда и только тогда, когда он образует схему силы к. В разделе 2.2.2 настоящей диссертации доказано обобщение свойства к-рсгулярности для совершенных 2-раскрасок графа Джонсона.

Позднее Д. Гордон в работе [35] заметил, что если существует 1-совер-шенный код в графе Джонсона 3{п) ги), то объем шара радиуса 1 в ^/(г^ги) является произведением различных простых чисел . ,рт. Более того, для всякого г е {1,. ,т} существует натуральное число с^, такое чтор"1 "близко" кп — ги, а ]Сге{1 п} "близко" к 2. Используя описанные выше свойства, Д. Гордоном был разработан теоретико-числовой алгоритм для проверки гипотезы Дельсарта для 1-совершенных кодов в J{n, ги) при фиксированных п и ги. Применяя этот алгоритм на компьютере, он показал несуществование 1-совершенных кодов в графах Джонсона для п < 2250.

Первые результаты, касающиеся полностью регулярных схем и кодов в дистанционно-регулярных графах (в частности в графах Джонсона) принадлежат Ф. Дельсарту [24]. Чтобы сформулировать эти результаты, приведем несколько дополнительных определений. Через < у < ги, обозначим примитивные идемпотенты, образующие базис схемы отношений Джонсона. Пусть С является кодом в графе Джонсона. Через х(С) обозначим характеристический вектор множества С в множестве вершин графа Джонсона J(n, т) - это вектор из 0 и 1, координаты которого соответствуют вершинам графа т). Координата вектора х(С), которой соответствует вершина кода С равна 1. Из Теорем 3.10 и 4.7 работы Ф. Дельсарта [24] следует, что сила кода С (код понимается как схема) в графе равна наибольшему числу удовлетворяющему равенствам

Е1Х(С) = Е2Х(С) = . - Е#(С) = 0.

Внешнее расстояние кода С было определено Ф. Дельсартом как число идемпотентов Етаких что выполнено Е^х{С) ^ 0, 1 < j < w. Ф. Дельсарт доказал (см. Теорему 5.13 в [24]) что если И - код в произвольном дистанционно-регулярном графе с внешним расстоянием в* и минимальным расстоянием 5, 5 > — 1, то такой код И является полностью регулярным.

В силу сложности подсчета в* иногда удобнее использовать следствия этого результата, полученные У. Мартином в [41]. Им показано, что всякая ¿-схема в J(n,w) с минимальным расстоянием 5, не меньшим, чем 2(ги — £) — 1, является полностью регулярной. Как прямое следствие этого факта произвольная {ги — 1) — (п, ги, А)-схема является полностью регулярной. Так как (и> — 1) — (п, и>, А)-схема имеет радиус покрытия 1 (то есть индуцирует совершенную 2-раскраску), это следствие имеет для нас особый интерес. А именно, из определения полностью регулярного кода по Ньюмайеру [44] вытекает, что, покрасив вершины этой схемы в белый цвет, а вершины, не принадлежащие схеме - в черный, получим совершенную 2-раскраску графа Джонсона. При этом матрица параметров этой совершенной раскраски равна (см. подробнее конструкцию 5 главы 1)

Л — 1 )w w(n — w — Л + 1) wX w(n — w — Л)

У. Мартином в [41] доказаны некоторые необходимые условия существования полностью регулярных схем. Им доказано, что для всякой полностью регулярной схемы в J(n, w) с минимальным расстоянием 5 имеет место неравенство 5 < (2ги+1)/3. Более того, если минимальное расстояние такой схемы не меньше чем 2а, то такая схема является а — (п, w, Аа)-схемой, где Аа > , а число блоков схемы не меньше C^l^}. С помощью полученных необходимых условий существования У. Мартином перечислены все полностью регулярные системы Штейнера силы 2 и все симметричные полностью регулярные схемы.

Другие результаты о полностью регулярных кодах в графах Джонсона получены А. Мейеровицем. В [42] ои доказал , что схема D является схемой силы 0 тогда и только тогда, когда D — {b Е J(n, w) : b С L] или D = {b E J(n,w) : b D L}, где L - некоторое подмножество множества {l,.,n}. Другими словами, полностью регулярная схема силы 0 является орбитой стабилизатора некоторых из п координат на множестве векторов длины п веса w в группе перестановок Sn.

У. Мартин в работе [40] предложил конструкцию полностью регулярной схемы, именуемой groupwise complete схемой. Пусть п — qpnui — sp, гДе р > 2 и q > 2s. Пусть {Xi,., Xq} - разбиение множества {1,., тг} на q подмножеств Xi, каждое мощности р. Пусть блоки D это С® подмножеств вида Ъ — Uie/Xj, где I пробегает все подмножества множества {1,.,д} мощности s. У. Мартин показал, что такая схема является полностью регулярной тогда и только тогда, когда выполнено одно из следующих трех условий: p=w, n=2w или р=2 или р=3, s=l. Несложно видеть, что описанные выше схемы (именуемые groupwise complete схемы) имеют силу 1 и минимальное расстояние р. В работе [40] У. Мартин доказал, что всякая полностью регулярная схема силы 1 с минимальным расстоянием большим или равным 2 является groupwise complete схемой.

Несмотря на ряд приведенных выше утверждений, множество вопросов, касающихся полностью регулярных равновесных кодов, остается открытым. Прежде всего не найдено эффективных критериев проверки, является ли данный код полностью регулярным или нет. Как следствие, не исследовано большое множество кодов, которые могли бы быть полностью регулярными. С другой строны, многие исследованные классы полностью регулярных кодов очень узки и поэтому соответствующие результаты носят частичный характер. Также недостаточно изучены наиболее интересные случаи (в контексте данной диссертации )- схемы большой силы с минимальным расстоянием 5 = 1 и покрывающим радиусом р = 1 (по сути дела, совершенные 2-раскраски).

Совершенные раскраски в два цвета произвольного радиуса бесконечной прямоугольной решетки исследовались М. Аксенович в работе [17]. В данном случае под совершенной раскраской радиуса г понимается раскраска вершин графа в множество цветов, при которой количество вершин цвета .7, находящихся на расстоянии, не больше г от вершины х цвета г, не зависит от выбора вершины х. М. Аксенович была описана часть совершенных 2-раскрасок, установлено, что необходимым условием существования остальных раскрасок является выполнение условия |ац — <221 + 1| < 4. Также ею были перечислены параметры всех совершенных 2-раскрасок радиуса 1. Совершенные раскраски бесконечной прямоугольной решетки были предметом кандидатской диссертации [10] С.А. Пузыниной. Ею доказано, что если существует совершенная раскраска радиуса 1 бесконечной прямоугольной решетки с матрицей параметров А, то существует также периодическая совершенная раскраска, чья матрица параметров совпадает с А.

Приведем краткое описание результатов настоящей диссертации. В первой главе приводится описание орбитного метода - классического способа построения таких комбинаторных объектов, как ¿-схемы, совершенные раскраски различных графов. С использованием орбитпого метода в этой главе получена серия как бесконечных, так и спорадических конструкций совершенных 2-раскрасок графов Джонсона, найдены параметры этих раскрасок.

Напомним, что автоморфизмом произвольного графа б? называется подстановка на множестве вершин графа, сохраняющая отношение смежности между вершинами. Совокупность таких преобразований относительно операции суперпозиции образует группу, обозначаемую АиЬ{(3). Очевидно, что такая группа является подгруппой группы где V - число вершин графа б. Пусть Н является некоторой подгруппой группы автоморфизмов графа С. Действие группы Н разбивает множество вершин графа (2 на непересекающиеся орбиты. Поставив орбитам в соответствие различные цвета, получим орбитную раскраску вершин графа О, соответствующую подгруппе Н группы автоморфизмов графа С. В [15] доказано, что всякая орбитная раскраска является совершенной.

В общем случае число цветов в орбитной раскраске может оказаться достаточно большим. В отдельных случаях число цветов в такой раскраске можно уменьшить.

Лемма 1. (Об объединении цветов) [9] Пусть существует совершенная раскраска в т цветов с матрицей параметров Атхт. Раскраска, получаемая из исходной объединением цветов в г групп . . . , Ьг: П ^з — 0; ц=1 г^г — {1) • • •, ттг} будет совершенной тогда и только тогда, когда для любых г, з 6 {1 ,.,т}, г ^ ] и для любых р, в £ Ьг выполнено условие

Под орбитиым методом в данной диссертации понимается метод построения совершенных 2-раскрасок п-вершинного графа, при котором множество вершин фиксированного цвета получается объединением некоторых орбит под действием некоторой подгруппы группы Бп.

С использованием описанного выше метода в параграфе 1.1 получены деь следующие бесконечные серии совершенных 2-раскрасок графов Джонсона:

Теорема. Для подходящего m существуют совершенные 2-раскраски графа Джонсона J(2ra, 3) со следующими матрицами параметров:

3(2га — 5) 6 \ ( З(т-З) 3га 4 (га -2) 2т - 1 у Д га - 2 5га -7

3(га — 1) 3(га-2) (га + 4) 5га - 13

Теорема. Существуют совершенные 2-раскраски графа J{2w,w) для подходящего w со следующими матрицами параметров: w{w- 2) 2w \ iw{w- 1)+2 гу-2 2(w - 1) (ги - I)2 + 1 ) U ^ 3w w{w - 3)

Перечислены все совершенные 2-раскраски графов Джонсона J(n, 2):

Утверждение 1. Матрица любой совершенной раскраски J(n, 2) имеет вид

2(п — 3) 2 \ I 2(п-а-2) 2а \ или , ' ч , п — 2 п-2 J у 2(п- 1 - а) 2(а - 1) J где 0 < а < п — 2, при четном п, «а = 2,4).,п-2) при нечетном п.

Код С — {у G Еп : wt(y) = w,x ^ у}, для произвольного х веса г будем называть шапкой (соответствующей вершине х). А. Мейеровиц в [42] показал, что этот код в графе J(n, w) является полностью регулярным. Слой с номером j в дистанционном расслоении относительно таких кодов будем для удобства обозначать Lj (х).

В главе 1 найден массив пересечений шапок и мощности слоев дистанционных разбиений относительно кодов-шапок.

Теорема 2. Пусть х является вектором веса i,i <w из Еп. Тогда: Для, всех 0 < j < i справедливо -Л(п - л> $ = (г- Лз + (м - г + ¿)(п - гу - Л> ¿(ш -1 +Л

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

В параграфе 2.1 получена система линейных соотношений, связывающих спектр белого цвета некоторой совершенной 2-раскраски относительно полностью регулярного кода. Из этой системы следует, что спектр белого цвета некоторой совершенной 2-раскраски относительно полностью регулярного кода определяется однозначно параметрами совершенной раскраски, массивом пересечений полностью регулярного кода и количеством белых вершин в полностью регулярном коде.

Пусть С является графом. Рассмотрим полностью регулярный код С в графе С и некоторую совершенную 2-раскраску графа С с множеством белых вершин ]¥. Через как выше, обозначим совокупность вершин графа на расстоянии у от кода С. Упорядоченный набор чисел {¿/(С) = \LjiC) П = 0,. ,р(С)}, назовем спектром множества белых вершин совершенной раскраски относительно полностью регулярного кода С.

Учитывая связь совершенных 2-раскрасок и полностью регулярных кодов из работы А. Ньюмайера [44] имеем

Утверждение 3. Пусть С - дистанционно регулярный граф. Тогда спектр множества белых вершин совершенной 2-раскраски графа О относительно вершины х не зависит от выбора вершины х, а зависит только от ее цвета и параметров совершенной раскраски.

В настоящей диссертации приведенное утверждение обобщено, а именно, показано, что спектр множества белых вершин совершенной 2-раск-раски графа С? относительно произвольного полностью регулярного кода С однозначно определяется массивом пересечений этого кода, количеством белых вершин в самом коде и матрицей параметров этого кода.

Теорема 3. Пусть существует совершенная раскраска графа С? в два цвета с матрицей А = {а^}*,.7=1,2 и полностью регулярный код С (в смысле Нъюмайера [44]) с массиволь пересечений в^, , 0 < 3 < р{С). Тогда имеют место соотношения: + Ц{С){а2\ — ац +

Щ) + = |^-(С)|а2Ь0 < 3 < р(С).

Таким образом, оказывается, что значения спектра связаны между собой системой линейных алгебраических уравнений с трехдиагональ-ной матрицей, задаваемой массивом пересечений кода С и параметрами совершенной 2-раскраски.

Данное свойство является обобщением свойства дистанционной инвариантности 1-совершепных кодов вп-кубе, установленного Г. С. Шапиро и Г. В. Злотником в [51]. С другой стороны, доказанное свойство является обобщением результата А. Ю. Васильевой [5] о спектре 1-совершенного кода гг-куба в дистанционном расслоении относительно полностью регулярного кода.

С учетом Теорем 2, 3 имеем следующее утверждение для совершенных 2-раскрасок графов Джонсона:

Следствие 1. Пусть суи^ествует совершенная 2-раскраска графа гу), х - произвольная вершина веса г. Тогда для всех 0 < < г выполняется жЦ4^ + 1^х)(а2\ - ац + бф + = С/С^^агь где = (г - ]){п -яи- ]), Щ = (г - ^ + (ги - г + ]){п - ги - э),

Т^ — ъи(п — ги) — й® —

Следствие 1 позволило использовать компьютер для решения вопросов существования совершенных 2-раскрасок графов Джонсона с заданной матрицей параметров. С использованием компьютера удалось доказать несуществование ряда совершенных 2-раскрасок графов Джонсона ги).

Пункт 2.2.1 носит вспомогательный характер. В нем приводятся необходимые определения и некоторые результаты К. Годсила и Г. Ройла [32], Д. Цветковича, М. Дуба и X. Захса [15], касающиеся связи собственных значений графов и собственных значений совершенных раскрасок, описание собственных подпространств собственных векторов графа Джонсона в терминах книги [34]. Эти результаты используются в пункте 2.2.2, где доказывается, что множество вершин белого цвета совершенной 2-раскраски является схемой силы t, находится явное выражение для ¿. Приведем необходимые определения этого параграфа.

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

Рассмотрим совершенную раскраску графа С? в произвольное число цветов. Собственным значением и собственным вектором совершенной раскраски с матрицей параметров Атхт графа С назовем собственные значения и собственный вектор матрицы АтХт. Связь между собственными значениями графа и совершенной раскраски этого графа дает следующее

Утверждение. [15] Всякое собственное значение совершенной раскраски графа (7 является собственным значением

Рассмотрим граф Джонсона ии). Собственные значения этого графа были найдены Дельсартом при исследовании схем отношений Джонсона.

Теорема 5. [24] Собственные значения графа Джонсона, Л^п,ги) исчерпываются следующими числами: (ги — к)(п—ги — к)—к, где 0 < к < т.

В разделе 2.2.2 доказывается следующее вспомогательное

Утверждение 4. Пусть суш^ествует совершенная 2-раскраска регулярного связного графа G степени t с матрицей параметров А = {ay}i'J=i,2- Тогда оба числа ац — a2i и t являются собственными значениями совершенной раскраски и собственными значениями графа G, причем ац — ац не равно t.

С учетом этого утверждения далее младшим собственным значением совершенной 2-раскраски регулярного графа будем называть число (ац — «21)) собственное значение, отличное от валентности этого графа.

Рассмотрим совершенную 2-раскраску графа Джонсона с матрицей А. Через к обозначим число п — 1 — л/(п -2w + I)2 + 4(ги + ац - а21)

2 '

Очевидно, что к зависит от n, w и параметров рассматриваемой совершенной 2-раскраски, но для краткости далее эту зависимость просто будем подразумевать. Основным результатом параграфа 2.2 является

Теорема 7. Пусть W является множеством белых вершин, совершенной 2-раскраски графа J(n, w) с матрицей параметров А = {a»j}ij=i,2. Тогда

1. младшее собственное значение ац — a2i равно собственному значению графа J(n, w) с номером к + 1, к > 0;

2. множество белых вершин этой совершенной раскраски W является к — (пли, —Щ1—C™~t)-cxeMou:

4 ' ' 012+021 п—к / '

3. множество W не является (к 4- 1) — (n,w, Х)-схемой.

Иными словами, множество белых вершин совершенной 2-раскраски графа Джонсона является схемой силы к.

Это свойство позволяет использовать необходимые условия существования i-схем для получения следующих необходимых условий существования совершенной 2-раскраски J(n, w) с заданной матрицей параметров.

Следствие 3. Пусть существует совершенная 2-раскраска графа J(n,w) с матрицей параметров А — {aij}ij=1,2, причем число ац — a2i является (к + собственным значением графа J{n)w). Тогда число а а"а ■ Сп-г* является целым для любого г, где 0 < г < к.

У. Мартин в [41] отметил, что (ги — 1) — (п, ги, Л)-схема индуцирует полностью регулярный код с радиусом покрытия 1. То есть из (ги — 1) — (п,ги, А)-схемы можно получить совершенную 2-раскраску, покрасив все векторы схемы в белый цвет, а векторы, не принадлежащие схеме - в черный.

Отсюда, принимая во внимание Теорему 7, получаем, что других совершенных раскрасок с младшим собственным значением, равным — ги не существует.

Следствие 5. Совершенная 2-раскраска J(n,w) с матрицей параметров А = {йу}г.,7=1,2, с собственным значением, равным —ги, существует тогда и только тогда, когда существует простая ги — 1) — (гг., ги,-—-(п — ги + 1)) — схема. а 12 + «21

Таким образом, класс совершенных 2-раскрасок включает в себя (ги — 1) — (тг, ги, А)-схемы, в том числе такие важные классы ¿-схем, как системы троек и четверок Штейнера, тесно связанные с совершенными и расширенными совершенными кодами соответственно.

В параграфе 2.3, используя тот факт, что подграф, индуцированный сферой радиуса 1 в графе Джонсона, изоморфен декартовому произведению двух полных графов, показывается, что параметр <221 совершенной 2-раскраски графа Джонсона оценивается снизу функцией от п,го,а 12-Доказательство этой теоремы сводится к нахождению решения некоторой дискретной экстремальной задачи.

Пусть Ь - некоторое целое число от 0 до ги(п — ги). Введем обозначение

Теорема 11. Пусть существует совершенная 2-раскраска графа J(n,w) с матрицей А = {а>г^^=1,2 такой, что ги < ] + 2. Тогда а21>п-5(а12) + 1-^1

Применяя Теорему 11, удалось доказать несуществование некоторых совершенных 2-раскрасок. Отметим, что эти раскраски удовлетворяют описанным выше необходимым условиям существования совершенных раскрасок, то есть Следствиям 1 и 3.

Следствие 4. Не существует совершенных раскрасок графов /(10,5), ¿/(12,4), 7(12,5), 7(12,6) с матрицами параметров: соответственно.

В параграфе 2.4 приведено дальнейшее развитие идей, изложенных в параграфе 2.3.

Для решения вопросов существования совершенных 2-раскрасок в параграфе 2.4 производится анализ структуры части совершенной раскраски графа Джонсона, на подграфе, индуцированном вершинами сферы радиуса 2. Отметим, что впервые аналогичный подход для решения вопросов существования совершенных 2-раскрасок (метод "локальных аргументов") был применен Д. Г. Фон-дер-Флаассом в [13] для доказательства необходимых условий существования совершенных раскрасок в два цвета графа гг-мерного куба Еп.

С использованием описанной выше идеи доказывается несуществование некоторых совершенных 2-раскрасок графов Джонсона с небольшими значениями параметра агь удовлетворяющих необходимым условиям существования совершенных 2-раскрасок, описанным в Следствиях 1, 3 и Теореме 11.

Теорема 12. Не существует совершенных 2-раскрасок графов 7(11, 3), 7(12,5), 7(13,4), 7(9,3) с матрицами соответственно. Кроме того, не существует совершенных раскрасок графа 7(12,4) с матрицами

14 18 4 28

С использованием разработанных в главе 2 необходимых условий существования совершенных раскрасок и конструкций, полученных в главе 1, в главе 3 перечислены параметры всех совершенных 2-раскрасок

Отметим различие задач перечисления параметров совершенных 2-раскрасок графов Джонсона и перечисления всех совершенных 2-раскрасок этих графов. Так как класс совершенных 2-раскрасок графов Джонсона включает в себя, помимо множества различных комбинаторных объектов различной структуры, системы троек Штейнера, то задача перечисления совершенных раскрасок не легче, чем задача перечисления всех систем троек Штейнера. Последняя задача далека от своего решения - лучшим на сегодняшний день является результат [45] П. Р. Д. Остергарда и П. Каски, перечисливших все неизоморфпые системы троек Штейнера порядка 19, которых оказалось 11084874829. В данной диссертации задачи перечисления всех неизоморфных совершенных 2-раскрасок графов Джонсона не решаются.

В параграфе 3.1 перечислены параметры всех совершенных 2-раскрасок графов Джонсона 7(6, 3).

Теорема 13. Матрицы параметров совершенных 2-раскрасок графа 7(6, 3) исчерпываются следующим списком: графов 7(6,3), 7(7,3), 7(8,3) и 7(8,4).

Основным результатом параграфа 3.2 является следующая

Теорема 14. Матрицы параметров совершенных раскрасок 7(7, 3) в два цвета исчерпываются следующим списком:

1)

2)

Отметим, что при этом совершенная раскраска ,7(7, 3) с матрицей (1) индуцирована стабилизатором одной из семи координат, а совершенные раскраски с матрицами (2) индуцироваиы однократной и двухкратной системами троек Штейнера соответственно. Принимая во внимание единственность (с точностью до переименования координат) этих объектов, получаем полное перечисление всех совершенных 2-раскрасок графа 7(7,3).

В параграфах 3.3 и 3.4 перечислены параметры совершенных 2-раскрасок графов 7(8, 3) и 7(8,4) соответственно. Для доказательства (в дополнение к совершенным 2-раскраскам, описанным в главе 1) построено несколько спорадических (т.е. таких, которые нельзя обобщить для бесконечного числа графов Джонсона) совершенных 2-раскрасок этих графов.

Теорема 15. Матрицы параметров совершенных 2-раскрасок графа 7(8,3) исчерпываются следующим списком:

Теорема 16. Матрицы параметров совершенных 2-раскрасок графа 7(8,4) исчерпываются следующим списком:

О 16 4 12

4 12 8 8

В главе 4 исследовались слабые изометрии выколотых кодов Препараты. Приведем несколько дополнительных определений.

Код С будем называть приведенным, если он содержит нулевой вектор. Два кода С\ и Сг длины п называются эквивалентными, если существует автоморфизм Р пространства Еп, такой что Р{С\) = С^- Отображение I : С\ —» С*2 двух кодов С\ и Со называется изометрией (а коды С\ и С2 изометричными), если д(х,у) — ¿{1{х),1{у)) выполнено для всех х и у из С\. Отображение J : С\ —■> называется слабой изометрией кодов С\ и С2 (а коды С\ и Сч слабо изометричными), если для всех х,у из С\ равенство с1(х,у) = й имеет место тогда и только тогда, когда J{y)) = с/, где ё, - кодовое расстояние кода С\. Граф минимальных расстояний кода С определяется как граф, множество вершин которого совпадает с множеством кодовых слов кода С; пару вершин ж, у полагают смежными при д{х, у) = с/, где й - кодовое расстояние кода С. Кодом Препараты Рп называется двоичный код длины п — 2т мощности 22т~2ш для четного т > 4 с кодовым расстоянием 6. Выколотый код Препараты (то есть код, полученный из кода Препараты удалением фиксированной координаты из всех кодовых слов) длины п — 2т — 1 будем обозначать через Рп. Коды Препараты и выколотые коды Препараты обладают целым рядом полезных свойств. В работе [12] Н. В. Семаков, В. А. Зиновьев и Г. В. Зайцев ввели понятие равномерно упакованного (в узком смысле) кода и доказали, что выколотый код Препарата является равномерно упакованным в узком смысле. Более того, в этой работе [12] авторы показали, что всякий равномерно упакованный в узком смысле код является полностью регулярным. Принимая во внимание упомянутую выше связь совершенных раскрасок и полностью регулярных кодов, этот результат объясняет актуальность исследований равномерно упакованных кодов (в частности кодов Препараты) в рамках темы настоящей диссертации.

В работе [4] JI. А. Бассалыго, Г. В. Зайцев, В. А. Зиновьев ввели обобщение понятия равномерно упакованного кода и показали, что этот класс кодов содержит коды Препараты. В работе [12] доказано, что множество вершин минимального веса приведенных кодов Препараты длины п образует 3 — (п, 6, (п — 4)/3)-схему (для выколотых кодов Препараты 2 — (п, 5, (п —3)/3)-схему соответственно). Кроме того, в работе [50] Н. В. Семаков, В. А. Зиновьев и Г. В. Зайцев показали, что любой выколотый код Препараты однозначно достраивается до 1-совершенного кода.

C.B. Августинович установил в [2], что всякие два слабо изометрич-ных 1-совершенных кода эквивалентны. В работе [43] доказано, что всякий расширенный 1-совершенный код восстанавливается с точностью до эквивалентности по своему графу минимальных расстояний. Для этого показано что всякой максимальной клике блочного графа системы четверок Штейнера, образованной кодовыми словами приведенного расширенного совершенного кода минимального веса, можно поставить в соответствие ровно одну координатную позицию. Как следствие восстанови-мости расширенного совершенного кода по графу минимальных расстояний, всякие два слабоизометричных расширенных 1-совершенных кода являются эквивалентными.

В параграфе 4.1 с помощью анализа свойств 2 —(п, 5, (п — 3)/3)-схемы, образованной кодовыми словами минимального веса приведенного выколотого кода Препараты длины п и модификацией подхода, примененного в [2], доказана следующая

Теорема 17. Пусть J : Р™ —> Р2" является слабой изометрией двух выколотых кодов Препараты Р™ и длины п. Тогда J является изометрией.

С учетом установленной C.B. Августиновичем и Ф.И.Соловьевой в [3] метрической жесткости (выколотых) кодов Препараты из Теоремы 20 вытекает, что слабоизометричные выколотые коды Препараты длины п > 210 — 1 являются эквивалентными, а группа автоморфизмов таких кодов изоморфна группе автоморфизмов графа минимальных расстояний этих кодов.

Следствие 8. Пусть п > 210 — 1. Два выколотых кода Препараты длины п слабоизометринны тогда и только тогда, когда они эквивалентны.

Следствие 10. Группа автоморфизмов выколотого кода Препараты длины п, п > 210 — 1 изоморфна группе автоморфизмов графа минимальных расстояний этого кода.

В параграфе 4.2 доказаны аналогичные результаты для кодов Препараты:

Теорема 20. Пусть 3 : Р[1 —> Р2" является слабой изометрией двух кодов Препараты Р™ и длины п. Тогда 3 является изометрией.

Следствие 11. Пусть п > 212. Два кода Препараты длины п являются слабоизометричными тогда и только тогда, когда они эквивалентны.

Следствие 13. Группа автоморфизмов кода Препараты длины п, п > 212 изоморфна группе автоморфизмов графа минимальных расстояний этого кода.

Актуальность данного результата подтверждается публикацией К. Т. Фелпса и К. Фернандес [31] (независимо полученной после представления автором диссертации статьи в журнал "Проблемы передачи информации"). В этой работе, с использованием метода максимальных клик, доказана однозначная восстановимость кода Препараты по графу его минимальных расстояний. В отличие от работы К. Т. Фелпса и К. Фернандес в настоящей диссертации слабые изометрии исследованы как для выколотых кодов Препараты, так и для кодов Препараты.

В Приложении приводятся результаты работы компьютерной программы, проверяющей выполнение разработанных в диссертации необходимых условий существования совершенных 2-раскрасок графов Джонсона 3(п,и;) при 9 < п < 13, см. Теорему 11 и Следствия 1 и 3.

1. Августинович C.B. Комбинаторные и метрические свойства совершенных кодов и раскрасок // Канд. дисс., Новосибирск. 2000. 33 с.

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

3. Августинович С.,В., Соловьева Ф.,И. О метрической жесткости двоичных кодов // Пробл. передачи информ. 2003. Т. 39. N. 2. С. 63-68.

4. Бассалыго Л. А., Зайцев Г. В., Зиновьев В. А. О равномерноупако-ванных кодах // Пробл. передачи информ. 1974. Т. 10. N. 1. С. 9-14.

5. Васильева А.Ю. Спектральные свойства совершенных двоичных (п,3)-кодов // Дискрет, анализ и исслед. операций. Т. 2. N. 2. С. 16-25, 1995.

6. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов // Москва, Наука. 1990. 384 с.

7. Зиновьев В. А., Леонтьев В.К. О совершенных кодах // (Пре-принт/ИППИ АН СССР). 1972. Вып. 1. С. 26-35.

8. Зиновьев В. А., Леонтьев В.К. Несуществование совершенных кодов над полями Галуа // Проблемы управления и теории информации. 1973. Вып. 2. С. 123-132.

9. Пузынина С.А. Совершенные раскраски бесконечной прямоугольной решетки // Канд. дисс., Новосибирск. 2008. 79 с.

10. Пулатов А.К. К структуре плотно упакованных (п,3)-кодов // Методы дискретного анализа в теории кодов и схем: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1976. Вып. 29. С. 53-60.

11. Семаков Н.В., Зиновьев В.А., Зайцев Г.В. Равномерно упакованные коды // Пробл. передачи информ. 1971. Т. 7. N. 1. С. 38-50.

12. Фон-дер- Флаасс Д.Г. Совершенные 2-раскраски гиперкуба // Сиб. мат. журн. 2007. Т. 48. N. 4. С. 923-930.

13. Фон-дер-Флаасс Д. Г. Совершенные 2-раскраски 12-мерного куба, достигающие границы корреляционной иммунности // Сиб. электрон, мат. изв. 2007. N. 4. С. 292-295.

14. Цветкович Д., Дуб М., Захс. X. Спектры графов: теория и применение // Киев, Наукова Думка. 1984. 384 с.

15. Ahlswede R., Aydinian Н.К., Khachatrian L.H. On Perfect Codes and Related Concepts // Designs, Codes and Cryptography. 2001. V. 22. P. 221-237.

16. Axenovich M. On multiple coverings of the infinite rectangular grid with balls of constant radius // Discrete mathematics. 2003. V. 268. P. 31-49.

17. Bannai E. Codes in bi-partite distance-regular graphs// J.London.Math. Soc. 1977 V. 2. P. 197-202.

18. Beth Т., Jungnickel D., Lenz H. Design Theory // Cambridge University Press 1999.

19. Biggs E. Perfect codes in graphs// J.Combin.Theory Ser.B. 1973. V. 15. P. 289-296.

20. Borges J., Rifa J., Zinoviev V.A. On non-antipodal binary completely regular codes // Discrete Mathematics 2008. V. 308 N. 16. P. 3508-3525.

21. Brouwer A.E., Cohen A.M., Neumaier A. Distance regular graphs, Berlin, Springer-Verl. 1989.

22. Dehon M. On the existence of 2-designs S\(2,3, v) without repeated blocks // Discrete Math. 1983. V. 43. P. 155-171.

23. Delsarte P. An Algebraic Approach to the Association Schemes of Coding Theory // Philips Res. Rep. Suppl. 1973. V. 10. P. 1-97.

24. Delsarte P. Bounds for unrestricted codes by linear programming, Philips Res. Reports. 1972. V. 27. P. 272-289.

25. Etzion Т., Hartman A. Towards a large set of Steiner quadruple systems // SIAM J. Discrete Math. 1991. V. 4. P. 182-195.

26. Etzion Т., Schwarz M. Perfect Constant-Weight Codes // IEEE Trans. Inform. Theory. 2004. V. 50. N. 9. P. 2156-2165.

27. Etzion T. Configuration Distribution and Designs of Codes in the Johnson Scheme // Journal of Combinatorial Designs. 2007. V.15. P. 1534.

28. Etzion T. On the nonexistence of perfect codes in the Johnson scheme // SIAM J.Discr.Math. 1996. V.9. N. 2. P. 201-209.

29. Fon-der-Flaas D. A bound on correlation immunity // Сиб. электрон, мат. изв. 2007. N. 4. С. 133-135.

30. Fernandez-Cordoba C., Phelps K. T. On the minimum distance graph of an extended Preparata code // Designs, Codes and Cryptography submitted.

31. Godsil C., Royle G. Algebraic Graph Theory // Springer Science+Business Media. LLC. 2004.

32. Godsil C., Praeger C., Completely transitive designs, preprint.

33. Godsil C. Association schemes // Combinatorics and Optimization. University of Waterloo. 2005.

34. Gordon M.D. Perfect Single Error-Correcting Codes in the Johnson Scheme // IEEE Trans. Inform. Theory. 2006. V. 52, N. 10. P. 4670-4672.

35. Hammond P. On the nonexistence of perfect codes and nearly perfect codes // Disc. Math. 1982. V. 39. P. 105-109.

36. Hanani H. On quadruple systems // Canad. J. Math. 1960. V. 15. P. 145-157.

37. Hartman A., Phelps K.T. Tetrahedral quadruple systems // Utilitas Math. 1990. V. 37. P. 181-189.

38. Johnson S. M. Upper bounds for constant weight error-correcting codes // Discr.Math. 1972. V. 3. P. 109-124.

39. Martin W. J. Completely Regular Designs of Strength One //J. Alg. Combin. 1994. V. 3. P. 17-185.

40. Martin W. J. Completely Regular Designs //J. Combin. Designs. 1998. V. 6. N. 4. P. 261-273.

41. Meyerowitz A. Cycle-balanced partitions in distance-regular graphs // Discr.Math. 2003. V. 264. P. 149-165.

42. Mogilnykh I.Yu., Ôstergârd P.R.J., Pottonen 0., Solov'eva F.I. Reconstructing Extended Perfect Binary One-Error-Correcting Codes from Their Minimum Distance Graphs // IEEE Trans. Inform. Theory. 2009. V.55. N. 6. P. 2622-2625.

43. Neumaier A. Completely regular codes // Discrete Mathematics. 1992. V. 106/107. P. 353-360.

44. Kaski P., Ostergârd P. R. J. , The Steiner triple system of order 19 // Math. Comp. 2004. V. 73. P. 2075-2092.

45. Phelps K.T., Stinson D.R., Vanstone S.A. The existence of simple 53(3,4,v) // Discrete Math. 1989. V. 77. P. 255-258.

46. Rifa J., Zinoviev V. A. On linear completely regular codes with covering radius /9—1. Construction and classification. // arxiv.org preprint. arXiv:0906.0550vl.

47. Rifa J., Zinoviev V. A. On the Kronecker Product Construction of Completely Transitive q-Ary Codes // LNCS, Springer. 2008. V. 5228. P. 163-170.

48. Roos C. A note on the existence of perfect codes in Johnson scheme// Discr.Math. 1983. V.47. P. 121-123.

49. Shapiro G. S., Slotnik D. S. On the mathematical theory of error correcting codes // IBM Journal of Research Development. 1959, V. 3. P. 68-72.

50. Teirlinck L. On large sets of disjoint quadruple systems // Ars Combinatoria. 1984. V.17. P. 173-176.53. van Tilborg H. C. A. Uniformly packed codes //Ph. D. Thesis, Eindhoven University of Technology, the Netherlands, 1975.

51. Tietavainen A. On the nonexistence of perfect codes over the finite fields // SIAM J.Appl. Math. 1973. V. 24. P. 88-96.Публикации автора по теме диссертации

52. Mogilnykh I. Yu. On k-regularity of perfect colorings of Johnson graphs in two colors // Proceedings of Tenth International workshop on Algebraic Combinatorial Coding Theory (ACCT-2006), P. 198-202. September 3-9 2006, Zvenigorod, Russia.

53. Могильных И.Ю. О регулярности совершенных раскрасок графа Джонсона в два цвета // Пробл. передачи информ. 2007. Т. 43. N 4. С. 37-44.

54. Mogilnykh I. Yu., Avgustinovich S. V. Perfect colorings of Johnson graph in two colors // Proceedings of XI International Symposium on Problems of Redundancy in Information and Control Systems, Saint-Peterburg, Russia, July 2-6, 2007. P. 205-209.

55. Avgustinovich S. V., Mogilnykh I. Yu. Perfect 2-colorings of Johnson graphs J(6, 3) and J(7,3) // LNCS, Springer, 2008. V. 5228. P. 11-19.

56. Могильных И.Ю. О слабых изометриях кодов Препараты // Пробл. передачи информ. 2009. Т. 45, N 2. С. 78-83.

57. Mogilnykh I. Yu. Weak isometries of Preparata codes // Pz'oceedings of XII International Symposium on Problems of Redundancy in Information and Control Systems (Saint-Peterburg, Russia, May 26-30, 2009). P. 96100.

58. Могильных И.Ю. О несуществовании некоторых совершенных 2-раскрасок графов Джонсона // Дискретн. анализ и исслед. опер. 2009. Т. 16. N 5. С. 52-68.

59. Августинович С.В., Могильных И.Ю. Совершенные раскраски графов Джонсона 7(8,-3) и J(8, 4) в два цвета// Дискретн. анализ и исслед. опер. 2010. Т. 17. N 2. С 3-1Q