Совершенные 2-раскраски графов Джонсона тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Могильных, Иван Юрьевич

• Могильных, Иван Юрьевич
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Могильных, Иван Юрьевич

Введение

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-раскраски графов Джонсона»

В данной диссертации исследуется вопрос существования совершенных 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.

Список литературы диссертационного исследования кандидат физико-математических наук Могильных, Иван Юрьевич, 2010 год

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