Собственные функции и кратные совершенные коды в графах Джонсона и Хэмминга тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Воробьёв, Константин Васильевич

• Воробьёв, Константин Васильевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Воробьёв, Константин Васильевич

Оглавление

Введение

1 Совершенные 2-раскраски гиперкуба

1.1 Основные определения и понятия

1.2 Известные конструкции

1.3 Итеративная конструкция и новые оценки на число совершенных 2-раскрасок гиперкуба

2 Кратные совершенные коды в гиперкубе

2.1 Основные определения и понятия

2.2 Связь совершенных 2-раскрасок и к-кратных совершенных кодов

2.3 Некоторые частные случаи

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

3.1 Основные определения и понятия

3.2 Действие преобразования Фурье на собственные функции графа Джонсона

3.3 Критерий вложимости собственных функций графа Джонсона

в собственные функции графа Хэммипга

3.4 Специальный случай критерия вложимости

Литература

Введение диссертации (часть автореферата) на тему «Собственные функции и кратные совершенные коды в графах Джонсона и Хэмминга»

Введение

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

Вершинами графа п-мерного куба (или двоичного графа Хэмминга,) являются все двоичные наборы длины щ вершины смежны, если соответствующие им наборы отличаются ровно в одной координате. Весом вершины у £ Нп называется количество единиц в этом наборе. Расстояние Хэмминга с1{х,у) между вершинами х,у Е Нп - это количество позиций, в которых х и у различны.

Графом Доюонсона 3(п.ш) называется граф, вершинами которого являются все двоичные наборы, содержащие в точности ъи единиц. Две вершины являются смежными, если соответствующие им наборы отличаются ровно в двух координатах. Расстояние между двумя вершинами х, у Е .7(п, из) определяется следующим образом: ¿,](х,у) = |с1н(х,у). Заданные выше расстояния dJ(x,y) и (1н{х,у) являются стандартными графскими метриками, то есть равны числу ребер в минимальном пути из х в у в графах ,1(п,гш) и Н" соответственно.

Отображение Т : V —> {1,2,... к} называется совершенной раскраской вершин графа С = (V. Е) в к цветов (совершенной /е-раскраской) с матрицей М = (^гу')гк} > 6СЛИ ОНО СЮръеКТИВНО И ДЛЯ каждых 1,2 У любой вершины цвета г число соседей цвета j равно гп^. Матрица М пазывает-

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

1-совершенные коды в произвольном графе также являются совершенными

2-раскрасками этого графа.

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

Исследованиями, посвященными совершенным 2-раскраскам »-мерного булева куба, занимался Д.Г. Фоп-Дер-Флаасс. В работе 2007 года [1] были получены первые необходимые условия на параметры возможных совершенных 2-раскрасок. Позднее этим же автором была получена так называемая граница корреляционной иммунности [2], которая позволила сформулировать существенное ограничение на параметры существующих совершенных 2-раскрасок n-куба. Раскраски, достигающие эту границу в 12-мерном кубе, были впоследствии изучены Д.Г. Фоп-Дер-Флаассом в [3].

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

Первые совершенные коды были построены Р. Хэммингом в 1950 году [4]. Зиновьев, Леонтьев и Тиетвайнен показали [5. 6]. что все возможные параметры 1-еовершенных кодов исчерпываются списком п — 2k — 1, г = 1 и п = 23, г = 3 для двоичного п-куба. В 1962 году Ю.Л. Васильевым

была предложена новая конструкция, которая впервые позволяла строить нелинейные 1-совершенные коды [7]. В частности, эта конструкция давала следующую нижнюю оценку числа различных 1-совершенных кодов в кубе размерности п — 1 = 2"1 — 1:

В{п- ...

В дальнейшем на основе метода ¿-компонент эта оценка была улучшена в работе [8|. Наилучшая на данный момент нижняя оценка была получена в [9]. Полученные на текущий момент верхние оценки [10, 11] существенно отличаются от нижних, что свидетельствует о том, что описание 1-совершснпых кодов ещё далеко от завершения.

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

Системой троек Штейнера называется такое семейство 3-х элементных подмножеств (блоков) некоторого п-элементпого множества Аг, что любая неупорядоченная пара элементов множества N содержится ровно в одном блоке этого семейства.

Подмножество вершин графа называется к-кратным совершенным кодом радиуса г, если для каждой вершины шар радиуса г с центром в этой вершине содержит в точности к кодовых вершин. В случае к = 1 получается классическое определение 1-совершенного кода.

Несмотря на то, что теория 1-совершенных кодов развивается уже долгое время, кратные совершенные коды в графе Хэмминга практически по изучались. Общая задача и некоторые результаты можно найти в [12, 13|. Кратные совершенные коды радиуса 1 в п-кубе можно получить, объединив произвольный 1-совершенный код в этом графе со сдвигом этого кода по какой-нибудь координате. Стоит отметить парадоксальное обстоятельство существования нерасщеплясмых совершенных кодов радиуса 1 и кратности 2. то есть таких кодов, которые не могут быть представлены в виде объединения 2-х совершенных кодов [14]. Как уже указывалось выше, задача перечисления параметров и и г, при которых существуют 1-совсршеппые коды, была

успешно решена в [5, 6]. В случае к -ф 1 такая задача для /¿-кратных совершенных кодов ещё далека от решения. В частности поэтому новые конструкции кратных совершенных кодов представляют большой интерес, особенно при п таких, что в графе Хэмминга размерности п не существует обычных l-совершенных кодов.

Проблема вложения одних комбинаторных объектов в другие также является классической проблемой в дискретной математике, теории графов и теории кодирования. Существует ряд интересных результатов, касающихся вложения одних структур в графе Хэмминга в другие. В частности, непосредственно из определения совершенного кода следует, что вершины веса 3 приведенного совершенного кода n-куба образуют систему троек Штейнера порядка п. Известно, что любая частичная система троек (четверок) Штейнера может быть вложена в систему троек (четверок) Штейнера некоторой длины [15]. В работе [16] был получен похожий результат для совершенных кодов: всякий код с расстоянием 3 может быть вложен в некоторый 1-совершенпый код большей длины.

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

Для произвольного неориентированного графа G = (V, Е) с матрицей смежности M функция / : V —> R называется собственной с собственным значением Л, если M/ = А/. Собственные функции являются одним из основных инструментов при работе с совершенными кодами и раскрасками различных классов графов. В данной диссертации исследуется вопрос вложимости собственных функций графа Джонсона в собственные функции графа Хэмминга.

Приведем краткое описание результатов настоящей диссертации. В пер-

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

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

а Ь \

, если каждая вершина

с д )

чёрного цвета имеет а соседей чёрного цвета и Ь соседей белого цвета, а каждая белая вершина имеет с соседей чёрного цвета и с/ соседей белого. По умолчанию будем считать, что Ь ^ с. Нам также понадобятся необходимые условия существования такой совершенной раскраски: а + Ь = с + с/ = п.

= 2т для некоторого натурального т, где (Ь,с) обозначает наибольший общий делитель Ь и с. (Общее определение совершенной раскраски и основные свойства см. в |1].)

Приведем следующее важное утверждение, которое показывает, что указанные выше необходимые условия существования являются в некотором смысле и достаточными [1].

Теорема 1. Для каждой пары Ь,с натуральных чисел, удовлетворяющих

}+■ ( а Ъ

тт^ = 2т, существует число о,о = а о (Ь, с) такое, что матрица

{ ' 1 ' уса + Ь-с

является м,атрицей совершенной раскраски гиперкуба тогда и только тогда, когда а ^ а^.

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

В параграфе 1.3. содержится описание новой итеративной конструкции, основанной на последовательном применении некоторых известных ранее конструкций. Новая конструкция позволяет строить совершенные 2-раскрас

вается совершенной с матрицей параметров

для многих матрид параметров.

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

Теорема 2. Множество матриц совершенных 2-раскрасок, полученных па п-м шаге алгоритма, есть в точности м)южество всех матриц вида

(2П+1 - с* - 1) * А; а* к (2п+1 - а)* к (а - 1) * к

Уа£%,а ф 2т, 2п + 1 ^ а ^ 2"+1 - 1.

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

Теорема 3. Пусть (6, с) = к > 1,6 + с = к ■ 2т, а ^ с — (Ь,с). Тогда

т-1

существует не менее П 2" с< различных совершенных 2-раскрасок с

?=о

матрицей параметров ( ], где (с,-) — некоторая неубывающая после-

\с д)

довательность натуральных чисел, со — с\ = 1, сш_1 = с/к.

Теорема 4. Пусть (Ь, с) = 1, Ь+с = 2т, а ^ с—(6, с), с > 1. Тогда существу-

т-1 Ля^г)-!

ет не менее В (2г<) — 1) • 22 'с' различны,х совершенных 2-раскрасок с матрицей параметров ( ], где (с^) — некоторая неубывающая по-

Vе

следовательность натуральных чисел, ц 6 {2,..., т — 1},

Сго — 1, 1 — с

и где В(2Н> — 1) — число различных совершенных кодов в кубе размерности 2г" - 1.

Результаты первой главы получены совместно с Д.Г. Фон-Дер-Флаассом и опубликованы в [31|

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

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

Известно, что любая функция / : Нп —> Ж единственным образом пред-ставима в следующем виде:

п

где (х, = - стандартное скалярное произведение. Величины /(¿)

7 = 1

называются коэффициентами Фурье, и выполняется следующее соотношение

/>) = £ (-1)м/(*), * е Я".

¿€ЯП

Задаваемое этой формулой преобразование также называют преобразованием, Фурье функции /.

Полиномом Кравчука степени к называется

к

Кк(х,п) = ^ЫУ

.7=0

X \ / п — X

Теорема 5. Совершенная раскраска с матрицей параметров ( ) яв-

с (1

ляется кратным совершенным кодом радиуса г тогда и только тогда, когда — 1, п — 1) = 0, при этом кратность кода к = ^ (¿) • В параграфе 2.3. проводится анализ этого критерия для небольших значений г. В частности, найдены совершенные 2-раскраски графа Хэммиига, которые являются кратными совершенными кодами радиуса 2, причем в графе Хэмминга этой размерности не существуют обычные совершенные коды. В частности, из критерия следует, что совершенные 2-раскраски с мат-/с-1 Ъ \

рицей параметров являются кратными совершенными кода-

Vе ь~ч

ми для любого нечетного радиуса г.

При г = 2 критерий принимает вид: п2 + п{ 1 —4.x) + 4х2 — Ах + 2 = 0, где

Ь+с '¿{Ь+с)-1±у/4(Ь+с)-7 ^ £

х = и, соответственно, п =-^-. 1аким образом, поиск матриц параметров совершенных 2-раскрасок. которые являются одновременно

кратными совершенными кодами радиуса 2, сводится к решению последнего уравнения в целых числах.

В заключение, в параграфе рассмотрен случай г = 3. В этом случае поиск матриц параметров таких совершенных 2-раскрасок, помимо указан-

с- 1 Ъ \

, сводится к решению в целых числах

с 6 — 1 у

2(6+с)-1±л/12(г>+с)-23 уравнения п =-1-.

Результаты главы 2 опубликованы в [32].

В третьей главе данной диссертации найден критерий вложимости собственной функции графа Джонсона ,/(п,?/;) с заданным собственным значением в некоторую собственную функцию графа Хэмминга Нп с заданным собственным значением. Приведем некоторые определения и утверждения.

Как и раньше, под графом Н" будем понимать двоичный п-мерный куб, или другими словами, граф Хэмминга размерности п. Определим г-а слои, графа Нп как множество ¿"(г) = {у Е Нп : 1иЬ(у) = г}.

Известно, что все собственные числа графа Н" исчерпываются множеством {п - 2г, 0 < г < п, г Е Щ [19].

Собственные числа графа Джонсона, определение которого дано выше, описываются множеством {Аг-(и>,п) = (ги — г)(п — ги — г) —г, 0 < г < ги, г £ [19].

Определим также полиномы Эберлейп [20]:

Пусть заданы множества М^Мг, М2 Я и определены функции /1 : М\ —> М, /2 : М2 —> К. Будем говорить, что функция /2 вложима в /1, если /\(х) = /2(ж) для всех х Е М<)- Другими словами, если сужение функции ¡\ па множество Мч совпадает с /9, то есть = /2-

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

ных выше матриц вида

В параграфе 3.2 устанавливается, что преобразование Фурье функции на S(r) можно представить как оператор индуцирования с некоторым коэффициентом, зависящим от г.

Предложение 2. Пусть д : Нп —> Ж, д ф 0 и = при этом д

- собственная функция графа Дэюонсопа J(n,w) с собственным значением Xt(w.n). Тогда для любого j, 0 < j < п функция §\s(j) является собственной функцией графа J(n,j) с собственным значением \i(j, п).

Далее в этом параграфе исследуется вопрос, в каком случае полученная функция не будет тождественно равна 0.

Для того, чтобы сформулировать следующее утверждение, введем обозначение:

J (-l)sKs{j, w)7 если w > s, Cj{s,w)=<

I ( -1 )W+JKS-Ul(j. n - w), если w < s. Предложение 3. Пусть g : Hn —>• R, g ф 0 и g\rrnKQi > = 0, при этом

I H \j[S)

~~ собственная функция графа Джонсона J(n,s), соответствующая собственному значению \j(s,n). Тогда = 0, если и 'только если

выполняется

IV

У] Cj(s, w)Ej(i, w, п) — 0.

j=0

Основываясь на предложении 3. в параграфе 3.3. найден критерий вло-жимости собственной функции графа Джонсона J(n,w) с заданным собственным значением в некоторую собственную функцию графа Хэмминга Н1'. Теорема 6. Ненулевая собственная функция графа J(n,w), соответствующая собственному значению Ai(w,ii), влоэ/сима в некоторую собст,венную функцию графа Нп с собственным значением п — 2s, если и только если выполняется,

W

£ Cj(s, w)Ej[г, w, п) ф 0. з=о

Используя конструктивный характер доказательства теоремы б, выводится явная формула для собственной функции графа Н'\ в которую вло-жима функция /г.

Следствие 2. Пусть 1ъ - ненулевая собственная функция графа ,1(п,ги) с

II!

собственным значением А¿(и>,п) и ^ С^з, и))Е]{г, ъи, п) ф О, тогда она вло-

■у=0

жим,а в собственную функцию / графа Нп с собственным значением п — 2в, где

£ ЦУ) Е

1(х) = -55-

Е СД^г^ЯДг^п)

Также найден критерий того, что предъявленная в следствии 2 функция / является единственной собственной в графе Н7', в которую возможно вложить исходную функцию Н.

Следствие 3. Такое влоэюение будет единственным, если и только если.

ш

выполняется С ¡(в, и))Е]{к, и>, п) ф 0 для всех к, 0 < к <ги.

5=0

Далее в параграфе 3.4. рассматривается случай й = ги, который представляет отдельный интерес, так как при этом ненулевые значения исходной функции к из теоремы 6 и её ненулевые коэффициенты Фурье расположены в па одном и том же слое б^и;).

В этом случае благодаря соотношению, связывающему определенные полиномы Кравчука и Эберлейн, полученному в [21], удается упростить критерий из теоремы 6.

Следствие 4. Пусть 1г(х) — ненулевая собственная, функция графа </(п, г/;), соответствующая собственному значению Xi(w,n), тогда она вложима в некоторую собственную функцию графа Нп с собственным значением, п — 2т, если и только если выполняется

— г, п — 2г) ф 0.

Опираясь на известную серию целочисленных корней полинома Кравчука, приводится следующее

Следствие 5. Собственная (функция графа Джонсона ,¡(2'ш, ги) с собственным числом, \ilw.2w) при нечетном, т — г не может быть вложена ни в какую собственную функцию графа Н2ш с собственным значением. 0. Результаты 3-ей главы опубликованы в [33|.

Глава 1

Совершенные 2-раскраски гиперкуба

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

В параграфе 1.1. приводятся необходимые определения и некоторые вспомогательные утверждения.

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

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

1.1 Основные определения и понятия

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

( а Ь\

матрицей параметров , если каждая вершина черного цвета имеет

Vе V

а соседей чёрного цвета и Ь соседей белого цвета, а каждая белая вершина имеет с соседей чёрного цвета и сI соседей белого. По умолчанию будем считать, что Ъ ^ с. Нам также понадобятся необходимые условия существования такой совершенной раскраски.

а + Ь^=с + д — п, (1.1)

Эт € N : ^ = 2т, (1.2)

(Ь,с)

где (/;, с) - это наибольший общий делитель Ь, с.

Далее в тексте, говоря о совершенной 2-раскраске с матрицей парамет-{ а Ь\

ров , будем подразумевать, что условия 1.1 и 1.2 выполнены, в част-

\ с й I

ности, в некоторых случаях вместо с1 будем писать п + Ь — с. Кроме того, известно, что условие 1.2 на 6, с является и достаточным условием существования (см. [1].) в следующем смысле:

Теорема 1. Для каоюдой пары Ъ,с натуральных чисел, удовлетворяющих 1.2, существует число ао г Лц (6, с) такое, что матрица

является матрицей совершенной раскраски гиперкуба тогда и только тогда, когда а ^ ао-

Наилучшей нижней оценкой па а,о на сегодняшний день является так называемая граница корреляционной иммунности (она имеет место в случае

Ь ф с): а о ^ ^Цр. Если а = ^р. то говорят, что совершенная раскраска достигает границы корреляционной иммунности (подробнее об этом можно посмотреть в [2, 3, 25]).

В соответствии с введёнными определениями ставится задача: найти о-о = а0 (6, с) для всех 6, с, а также определить, сколько существует различных совершенных раскрасок с заданными параметрами. В данной работе приводится конструкция, которая даёт нижнюю оценку на число совершенных раскрасок с некоторыми заданными параметрами.

1.2 Известные конструкции

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

. а Ъ\ ( а + 1 Ь 1. | I ~М I — этн конструкция по одной существу-

с й ] \ С б/ + 1

ющей совершенной раскраске строит одну совершенную раскраску с новыми параметрами.

а 6 \ ( к ■ а к ■ Ъ \

—> — эта конструкция также по одной суще-

с. в, I \ к ■ с к ■ <1 I

ствующей совершенной раскраске строит одну совершенную раскраску с новыми параметрами.

Более подробно о них можно прочитать в [1].

3. Следующая конструкция является обобщением конструкции 3 из [1] для случая к = 1, так как в конструкции 3 не было указано на возможность несколькими способами получить совершенные раскраски с искомой матрицей параметров, это было сделано лишь одним способом.

, , . а Ь\ ( а - 1 26 + с .

а -> , а ^ 1, с ^ а + 1.

1 Х с (1 ) \ с а + 26 + с — 1

, ч . а 6

• л

с а

Ниже будут приведены описание этой более общей конструкции и необходимые доказательства. Конструкция состоит из двух шагов, представленных здесь двумя леммами.

Лемма 1. Пусть Т : Нп —> {0, 1} — совершенная раскраска в 2 цвета с

.матрицей параметров ( ] , и пусть а ^ 1. Тогда существует совер-

\с Л)

шейная раскраска в 3 цвета X : Н2'1 —> {+, —, 0} с матрицей парамет-

/а-1 а + 1 2 Ъ\ ров а + 1 а - 1 2Ь \ с с 2с1 )

, причём количество таких раскрасок не менее

Доказательство. Рассмотрим 2п-мерпый куб Я2" со следующей раскраской: Т\{х\,уъх2,уг> —,хп,уп) = Т{х 1 + гл. ...хп + уп). Нетрудно понять, что

( 2 а 2 Ъ

получившаяся раскраска в 2 цвета будет совершенной с матрицей I

Теперь рассмотрим множество М вершин вида V = (г>1, О, г>2, 0, ...уп, 0). М яв-

/а 6 \

ляется, по существу, графом Нп с совершенной раскраской . Исполь-

Vе

зуя то, что граф, индуцированный на чёрных вершинах, будет двудольным и регулярным степени а ^ 1, по теореме Кёпига-Холла о системе различных представителей (см. например [22]) на множестве М можно выделить совершенное паросочетание на чёрных вершинах. Таким образом, все чёрные вершины этого множества разбиваются на пары. По построению Н2п каждой вершине у Е М соответствует множество Д. определяемое соотношением: Учи Е Д \/г Е {1, 2,... п} У{ = г^2г-1 © гУ2г, где ф - сложение по модулю 2. Из строения Д понятно, что \/г>\/ги ((у ф и>) —> (Д П Ди = 0)) и и Д = Я2", а

иел/

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

Возьмём пару чёрных вершин у и и) из заданного выше паросочетания. Рассмотрим Ау, из его строения понятно, что расстояние между любыми двумя его вершинами чётно, а минимальное расстояние равно 2. Зададим на Д отношение "соседства": две вершины из Д будем называть "соседними", если расстояние между ними равно 2. Из определения Д. следует, что получившийся граф с вершинами из Д и отношением "соседства" вместо смежности, — это п-мерный куб. Покрасим его в 2 цвета ("+", "—") следующим образом. Возьмём вершину у = {у\, 0, г>2, 0, 0) (из Ау), покрасим её в цвет "+", далее рассмотрим какого-нибудь её "соседа" и в Д,. В исходном гиперкубе вершины у, и были на расстоянии 2. значит, есть ровно одна такая пара

вершин у',и1, что вместе они образуют цикл длины 4. Заметим, что из определения Ау следует, что вершины у', и' либо одновременно лежат в Аш, либо одновременно лежат вне Аг„. В первом случае покрасим вершину и в тот же цвет, что и вершину у (то есть в "+"), иначе в противоположный ("—")• Проделаем такую операцию для всех "соседей" у. Далее применим тот же алгоритм для всех соседей у, и т.д. В итоге всё Ау будет покрашено в 2 цвета ("+" и "—"). Далее введённое отношение "соседства" нам уже не понадобится, поэтому, говоря, что "вершины соседние", будем отождествлять это с "вершины смежны".

Теперь рассмотрим Аи>, у каждой вершины ги' е Аи, есть ровно 2 соседа из Ау, причём они одного цвета (оба "+" или оба "—"). Тогда покрасим вершину гу'в противоположный цвет. Итак, пара Аа, Аш покрашена. Заметим, что мы могли сделать это двумя способами (достаточно положить цвет вершины у равным "—", а не "+"). Проделаем такую операцию для всех пар из совершенного паросочетания. Все вершины 2п-мерпого куба, покрашенные в белый цвет покрасим в цвет 0. В итоге мы получили раскраску Н2п в 3 цвета. Осталось только убедиться, что она — совершенная с искомыми параметрами. Заметим, что если у произвольной вершины нашего Н2п есть сосед в какой-нибудь 2-компонентс и при этом она сама в ней не лежит, то у неё есть ещё ровно один сосед в этой 2-компонентс, причём его цвет отличен от цвета первого соседа. Теперь рассмотрим произвольную вершину цвета 0. Используя замечание, получаем, что у неё с соседей цвета "+", с соседей цвета "—" и 2(1 соседей цвета 0, так как белая вершина имела столько соседей белого цвета до перекрашивания белых вершин в цвет 0. Рассмотрим теперь произвольную вершину цвета "+". По построению она находится в какой-то 2-компоненте и имеет ровно 2 соседа в этой же компоненте, причём оба цвета "—". Она также имеет соседей ещё в а — 1 2-компоненте, так как до перекрашивания она была чёрной, и у неё было 2а чёрных соседей. В итоге получаем, что вершина цвета "+" видит а — 1 вершину цвета "+", а + 1 вершину цвета "—". 26 вершин цвета 0. Аналогично получаются искомые параметры для вершины цвета "—". Когда внутри каждой 2-компоненты мы красили вершины в цвета "-г " и "—", мы могли сделать это двумя способами. Так как число

Список литературы диссертационного исследования кандидат наук Воробьёв, Константин Васильевич, 2013 год

Литература

[1] Фон-Дер-Флаасс, Д. Г. Совершенные 2-раскраски гиперкуба / Д. Г. Фон-Дер-Флаасс // Сибирский математический журнал. - 2007. Т. 48. № 4. -С. 923-930.

[2] Fon-Der-Flaass, D. G. A bound on correlation immunity / D. G. Fon-Der-Flaass // Siberian Electronic Mathematical Reports. - 2007. - Vol. 4. - P. 133- 135.

[3] Фон-Дер-Флаасс, Д. Г. Совершенные 2-раскраски 12-мерного куба, достигающие границы корреляционной иммунности / Д. Г. Фон-Дер-Флаасс// Сибирские Электронные Математические Известия. - 2007. - Т. 4. - С. 292-295.

¡4] Hamming, R. W. Error detecting and errorcorrecting codes / R. YV. Hamming /,/ Bell Syst.Tech.J. - 1950. - Vol. 29. - P. 147-160.

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

[6] Tietavain en, A. On the nonexistence of perfcet codes over the finite fields/ A. Tietavain en,/,/ SIAM J.Appl. Math. - 1973. Vol. 24. -P. 88-96.

[7] Васильев, Ю. Jl. О негрупповых плотно упакованных кодах / Ю. Л. Васильев // Проблемы кибернетики. - М: Физматгиз, 1962. - Т. 8. - С. 337-339.

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

[9] Krotov, D.S. On the Number of 1-Perfect Binary Codes: A Lower Bound / D.S. Krotov, S.V. Avgustinovich // IEEE Transactions on Information Theory. - 2008. - Vol. 54, № 4. - P. 1760-1765.

[10] Августинович, C.B. Об одном свойстве совершенных двоичных кодов /

C. В. Августинович // Дискретн. анализ и исслед. опер. - 1995. - Т. 2, № 1. - С. 4-6.

[11] Сапоженко, A.A. К вопросу о числе совершенных кодов / A.A. Сапо-женко // XVI Международная конференция "Проблемы теоретической кибернетики": труды конференции. - Н.Новгород: Изд-во Нижегородского госуниверситета. - 2011. - С. 416-419.

[12] Cohen, G.D. Covering Codes / G. D. Cohen, I. S. Honkala, S.N. Litsyn. A. C. Lobstein. - Amsterdam: Elsevier, 1997. - 542 p.

[13] Van Wee, G. J. M. A note on perfect multiple coverings of the Hamming space / G. J.M. van Wee, G.D. Cohen, S.N. Litsyn // IEEE Trans. Inf. Theory. -1991. - Vol. 37, №. 3. -P. 678-682.

[14] Кротов, Д. С. О кратных МДР- и совершенных кодах, пе расщепляемых на однократные/ Д. С. Кротов, В. Н. Потапов// Пробл. передачи информ.

2004. - Т. 40, № 1. - С. 6-14.

[15] Linder, С. С. A survey of embedding theorems for Steiner systems / С. С. Linder// Ann. Discrete Math: Topics on Steiner Systems. - 1980. - Vol. 7. -P. 175-202.

[16] Avgustinovich, S.V. Embedding in a Perfect Code / S.V. Avgustinovich,

D. S. Krotov // Journal of Combinatorial Designs. - 2009. - Vol. 17, № 5. - P. 419-423.

[17] Августинович, С. В. Вычисление центрированной функции по ее значениям па средних слоях булева куба/ С. В. Августинович, А.Ю. Васильева// Дискретн. анализ и исслед. опер. - 2003. - Сер. 1, Т. 10, Я5 2. - С. 3-16.

[18] Августииович, С. В. Теоремы восстановления для центрированных функций и совершенных кодов/ С. В. Августииович, А. Ю. Васильева// Сиб. матем. журн. - 2008. - Т. 49, № 3. - С. 483-489.

[19| Дельсарт, Ф. Алгебраический подход к схемам отношений теории кодирования / Ф. Дсльсарт. - М.: Мир, 1976. - 136 с.

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

[21] Васильева, А.Ю. О реконструктивных множествах вершин в булевом кубе / А.Ю. Васильева// Дискрет, анализ и исслед. операций. - 2012. Т. 19, № 1. - С. 3-16.

[22] Холл, М. Комбинаторика/ М. Холл. - М.: Мир, 1970. С. 64-79.

[23] Habsieger, L. Integer Zeros of q-Krawtchouk Polynomials in Classical Combinatorics / L. Habsieger // Journal Advances in Applied Mathematics.

- 2001. - Vol. 27, №. 2-3. - P. 427-437.

[24] Krasikov, I. On integral zeros of Krawtchouk polynomials / I. Krasikov, S. Litsyn // Journal of Combinatorial Theory Series A. - 1996. - Vol. 74, №. 1.

- P. 71-99.

[25] Кротов, Д. С. О совершенных раскрасках половинного 24-куба / Д. С. Кротов // Дискрентый анализ и исследование операций. - 2008. - Т. 15, №. 5. - С. 35-46.

[26] Nagell, Т. The Diophantine equation х2 + 7 = 2"/ Т. Nagell // ARKIV FOR MATEMATIK. - 1960. Vol. 4, №. 2-3. - P. 185-187.

[27] Потапов, В. H. О совершенных раскрасках булева n-куба и корреляционно-иммунных функциях малой плотности / В. Н. Потапов // Сибирские Электронные Математические Известия. - 2010. - Т. 7.

- С. 372-382.

[28] Martin, W.J. Completely Regular Designs / W. L. Martin // Journal of Combinatorial Designs. - 1998. - Vol. 4. - P. 261-273. '

[29] Martin, W.J. Completely Regular Designs of Strength One / W. L. Martin // J. Alg. Comb. - 1994. - Vol. 3. - P. 177-185.

[30] Avgustinovich. S. V. Induced perfect colorings / S. V. Avgustinovich, I.Yu. Mogil'nykh// Сиб. электрон, матем. изв. - 2011. - Т. 8. - С. 310-316.

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

[31] Воробьёв, К. В. О совершенных 2-раскрасках гиперкуба / К. В. Воробьёв, Д. Г. Фон-Дер-Флаасс // Сибирские электронные математические известия. - 2010. - Т. 7, № 5. - С. 65-75.

[32] Воробьёв, К. В. О связи совершенных 2-раскрасок с кратными совершенными кодами в гиперкубе / К. В. Воробьёв // Мальцевские чтения 2011: труды конференции. - Новосибирск: Новосиб. гос. ун-т, 2011. - С. 33.

[33] Воробьёв, К. В. О вложении собственных функций графа Джонсона в собственные функции графа Хэмминга / К. В. Воробьёв // Дискрет, анализ и исслед. операций. - 2013. - Т. 20, № 5. - С. 3-12.

[34] Воробьёв, К. В. О числе совершенных 2-раскрасок гиперкуба / К. В. Воробьёв // XLVI Международная научная студенческая конференция "Студент и научно-технический прогресс Математика: труды конференции. -Новосибирск: Новосиб. гос. ун-т, 2008. - С. 182.

[35] Воробьёв, К. В. Кратные совершенные коды в гиперкубе / К. В. Воробьёв // Дискрет, анализ и исслед. операций. - 2012. - Т. 19, № 4. - С. 60-65.

[36] Vorobev, K.V. On the embedding of Jonson graph's eigenfunctions to Hamming graph's eigenfunctions / К. V. Vorobev// Workshop on Algebraic Graph Theory: conference proceedings. - Laramie, USA, 2013. P. 18.