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

Воробьёв, Константин Васильевич

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

Воробьёв, Константин Васильевич АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Новосибирск МЕСТО ЗАЩИТЫ

2013 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

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

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

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ МАТЕМАТИКИ им. С. Л. Соболева

СОБСТВЕННЫЕ ФУНКЦИИ И КРАТНЫЕ СОВЕРШЕННЫЕ КОДЫ В ГРАФАХ ДЖОНСОНА И ХЭММИНГА

01.01.09 - дискретная математика и математическая кибернетика

На правах рукописи

ВОРОБЬЁВ Константин Васильевич

АВТОРЕФЕРАТ

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

5 ДЕК 2013

Новосибирск 2013

005541930

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук

Научный руководитель:

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

Августинович Сергей Владимирович.

Официальные оппоненты:

Пяткин Артём Валерьевич, доктор физико-математических наук. доцент, Федеральное государственное бюджетное учреждение науки Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук, ведущий научный сотрудник; Гаврилкж Александр Львович, доктор физико-математических наук, Федеральное государственное бюджетное учреждение науки Институт математики и механики им. H.H. Красовского Уральского отделения Российской академии наук, старший научный сотрудник.

Ведущая организация:

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Московский государственный университет имени М.В. Ломоносова».

Защита состоится 25 декабря 2013 года в 16 часов на заседании диссертационного совета Д 003.015.01 при Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук по адресу: 630090, г. Новосибирск, пр. Академика Коптюга, 4.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института математики им. С. Л. Соболева Сибирского отделения Российской академии наук.

Автореферат разослан " Х2 " ыоясра 2013 г.

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

д.ф.-м.н. У/7/? Ю. В. Шамардин

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

Актуальность темы

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

Вершинами графа n-мерного куба (или двоичного графа Хэмминга) являются все двоичные наборы длины п; вершины смежны, если соответствующие им наборы отличаются ровно в одной координате. Весом wt(y) вершины у 6 Нп называется количество единиц в этом наборе. Расстояние Хэмминга d(x, у) между вершинами х,у £ Нп — это количество позиций, в которых х и у различны.

Графом Джонсона J(n, w) называется граф, вершинами которого являются все двоичные наборы, содержащие в точности w единиц. Две вершины являются смежными, если соответствующие им наборы отличаются ровно в двух координатах. Расстояние между двумя вершинами х, у Е J(n, w) определяется следующим образом: dj(x,y) = ^djj(x,y). Заданные выше расстояния dj(x,y) и dtf(x, у) являются стандартными графскими метриками, то есть равны числу ребер в минимальном пути из х в у в графах J(n, w) и Нп соответственно.

Отображение Т : V —> {1,2,... к} называется совершенной раскраской вершин графа G = (У, Е) в к цветов (совершенной к-раскраской) с матрицей М = если оно сюръективно

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

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

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

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

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

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

£(п-1)>227 7 • 2 Т • 2 * •••

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

оценки [10, 11] существенно отличаются от нижних, что свидетельствует о том, что описание 1-совершенных кодов ещё далеко от завершения.

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

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

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

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

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

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

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

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

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

Научная новизна. Все результаты, представленные в диссертации, являются новыми.

1. Получена конструкция, позволяющая строить совершенные рас-

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

с — (6, с) для всех допустимых пар (Ь, с). Как следствие, получена нижняя оценка на число различных совершенных 2-раскрасок с заданной матрицей параметров, которая является наилучшей на сегодняшний день.

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

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

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

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

Апробация работы. Результаты работы прошли апробацию на следующих международных конференциях: на конференции "Мальцевские чтения (Новосибирск, 2011); Международной конференции по алгебраической теории графов (Ларами, США, 2013 г.). Результаты диссертации докладывались на семинаре "Теория кодирования" , семинаре лаборатории "Дискретный Анализ" и семинаре лаборатории "Теория Графов" НГУ и Института матема-

тики СО РАН, семинаре отдела алгебры и топологии Института математики и механики УРО РАН.

Результаты диссертации отмечены дипломом Международной Студенческой Научной Конференции (МНСК-2008).

Публикации. Основные результаты диссертации получены автором самостоятельно и опубликованы в журналах из списка ВАК [23], [24]. Полученные автором совместно с Д.Г. Фон-Дер-Флаассом результаты работы [22] включены в неё для полноты изложения. Работы [25, 26, 27] являются тезисами докладов автора на различных конференциях.

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

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

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

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

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

Объем и структура диссертации. Диссертация состоит из введения, трех глав и списка литературы (36 наименований). Объем диссертации 52 страницы.

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

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

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

ного цвета и Ь соседей белого цвета, а каждая белая вершина имеет с соседей чёрного цвета и с? соседей белого. По умолчанию будем считать, что Ь ^ с. Нам также понадобятся необходимые условия существования такой совершенной раскраски: а + Ь = с+ с? = п, = 2т для некоторого натурального т, где (6, с) обозначает наибольший общий делитель Ь и с. (Общее определение совершенной раскраски и основные свойства см. в [1].)

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

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

краски гиперкуба тогда и только тогда, когда а ^ ао-

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

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

матрица

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

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

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

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

/ - а- 1)*к а* к \

\ (2"+1 — а) * к (а - 1) * к ) '

Уа € Ъ, а ф 2т, 2п + 1 < а ^ 2П+1 - 1.

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

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

"1-1 к(2*-1)-г

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

г=о

раскрасок с матрицей параметров ^ ^ ^ гс'е (сг) — некоторая

неубывающая последовательность натуральных чисел, со = с\ = 1) ст—1 = с/к.

Теорема 4. Пусть (6, с) = 1,6 + с = 2т, а ^ с — (Ь, с), с > 1. Тогда существует не менее В (2го - 1) • П 2 с< различных

г=го

совершенных 2-раскрасок с матрицей параметров ^ с ^ у где

((н) — некоторая неубывающая последовательность натуральных чисел, г'о € {2,..., тп — 1}, С(0 = 1, ст_1 = с и где В(2го — 1) — число различных совершенных кодов в кубе размерности 2го — 1.

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

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

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

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

А*) = ¿г Е М)^'0М * € Я",

tetfn

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

¿=1

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

{6 Я"

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

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

Теорема 5. Совершенная раскраска с матрицей параметров является кратным совершенным кодом радиуса г тогда и только

( а Ь

I ей

тогда, когда

— 1, п — 1) = 0, при этом кратность кода к = (™) •

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

В частности, из критерия следует, что совершенные 2-раскраски (с-1 Ь \

с матрицей параметров I ^ _ ^ I являются кратными со-

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

При г = 2 критерий принимает вид: п2+п( 1—4х)+4:г2—4х+2 =

Ь+с 2(Ь+с)-1±л/4(Ь+с)-7 „ О, где х — ^ и, соответственно, п =-^-. 1аким образом, поиск матриц параметров совершенных 2-раскрасок, которые являются одновременно кратными совершенными кодами радиуса 2, сводится к решению последнего уравнения в целых числах.

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

(с-1 Ъ \

помимо указанных выше матриц вида I Ь — 1 /' СВ0ДИТСЯ

2(6+с)-1±Л/12(Ы-с)-23

к решению в целых числах уравнения п =-^-.

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

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

Как и раньше, под графом Нп будем понимать двоичный п-мерный куб, или другими словами, граф Хэмминга размерности п.

Определим г-й слой графа Нп как множество 5(г) = {у € Нп : = г}-

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

Собственные числа графа Джонсона, определение которого дано выше, описываются множеством {АДги, п) = (го — г)(п — ги — г) —

г, 0 < г < и, г&Ъ) [19].

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

Пусть заданы множества М\, М-2, МгСМ^и определены функции Д : М\ —» М, /2 : М2 —> М. Будем говорить, что функция /2 вложима в /1, если /1(2;) — /2(2.') для всех х е М2. Другими словами, если сужение функции /1 на множество М2 совпадает с /2, то

есть Л|м2 = /2-

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

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

Предложение 1. Пусть д : Нп —>■ М, д ф 0 и 5|яп\5(ш) —

при этом - собственная функция графа Джонсона J(n,w)

с собственным значением А ¿(и;, п). Тогда для любого ], 0 < ] < п функция З^у) является собственной функцией графа J(n,j) с

собственным значением А¿0?, тг)-

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

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

С,-(я, и;)

(—1 укз(],ю), если го > в, (—1)и)+:>п — ги), если т < в.

Предложение 2. Пусть д : Нп —> М, д ф 0 и <7|яп\5(5) = 0; пРи этом д\а/ ч - собственная функция графа Джонсона J(n,s), соответствующая собственному значению Аг(в,гг). Тогда = 0,

если и только если выполняется

У^ w)Ej(i, и), п) = 0. 3=0

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

Теорема 6. Ненулевая собственная функция графа J(n,w)! соответствующая собственному значению А¿(ги, п), вложима в некоторую собственную функцию графа Нп с собственным значением п — 2в, если и только если выполняется

<7,-(в, У)Щ(г, го, п) ф 0.

з=о

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

Следствие 1. Пусть ¡г - ненулевая собственная функция графа

Л(п,и)) с собственным значением A¿('Ш, п) и ^ С^8,ги)Е]{ъ,11),п) ф

з=о

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

Е Чу) Е (-1)<х'4>

/(*) = -Ъ-

3=0

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

Следствие 2. Такое вложение будет единственным, если и толъ-

■ш

ко если выполняется С^в, ги, п) ф 0 для всех к, О < к <

з=о

и>.

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

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

Следствие 3. Пусть к{х) — ненулевая собственная функция графа соответствующая собственному значению А ¿(ги, п), тогда она вложима в некоторую собственную функцию графа Нп с собственным значением п — 2т, если и только если выполняется

Кги-{(т — г, п — 2г) ф 0.

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

Следствие 4. Собственная функция графа Джонсона J(2w,w) с собственным числом \{(и), 2ъи) при нечетном не может быть вложена ни в какую собственную функцию графа Н2ш с собственным значением 0.

Результаты 3-ей главы опубликованы в [24].

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

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

[8] Августинович, C.B. Построение совершенных двоичных кодов последовательными сдвигами ¿-компонент / C.B. Августинович, Ф.И. Соловьева // Пробл. передачи информ. - 1997. - Т. 33, m 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] Августинович, С.В. Об одном свойстве совершенных двоичных кодов / С. В. Августинович // Дискретн. анализ и исслед. опер.

- 1995. - Т. 2, № 1. - С. 4-6.

[11] Сапоженко, А. А. К вопросу о числе совершенных кодов / А. А. Сапоженко // 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] binder, С. С. A survey of embedding theorems for Steiner systems / С. C. binder// 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] Августинович, С. В. Вычисление центрированной функции no ее значениям на средних слоях булева куба/ С. В. Августинович, А.Ю. Васильева// Дискретн. анализ и исслед. опер. -2003. - Сер. 1, Т. 10, № 2. - С. 3-16.

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

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

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

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

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

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

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

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

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

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

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

Подписано в печать 08.11.2013 г. Печать цифровая. Бумага офсетная. Формат 60x84/16. Усл. печ. л. 2 Тираж 100 экз. Заказ № 185

Отпечатано в типографии «Срочная полиграфия» ИП Малыгин Алексей Михайлович 630090, Новосибирск, пр-т Академика Лаврентьева, 6/1, оф.104 Тел. (383) 217-43-46, 8-913-922-19-07

Текст научной работы диссертации и автореферата по математике, кандидата физико-математических наук, Воробьёв, Константин Васильевич, Новосибирск

04201 453023

на правах рукописи

Воробьёв Константин Васильевич

СОБСТВЕННЫЕ ФУНКЦИИ И КРАТНЫЕ СОВЕРШЕННЫЕ КОДЫ В ГРАФАХ ДЖОНСОНА И ХЭММИНГА

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

кибернетика

Диссертация

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

Научный руководитель к.ф.-м.н. С. В. Августинович

Новосибирск 2013

Оглавление

Введение 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература 48

Введение

Вершинами графа п-мерного куба (или двоичного графа Хэмминга,) являются все двоичные наборы длины щ вершины смежны, если соответствующие им наборы отличаются ровно в одной координате. Весом вершины у £ Нп называется количество единиц в этом наборе. Расстояние Хэмминга с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].

Первые совершенные коды были построены Р. Хэммингом в 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-совершенных кодов развивается уже долгое время, кратные совершенные коды в графе Хэмминга практически по изучались. Общая задача и некоторые результаты можно найти в [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. Для каждой пары Ь,с натуральных чисел, удовлетворяющих

}+■ ( а Ъ

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

{ ' 1 ' уса + Ь-с

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

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

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

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

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

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

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

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

Теорема 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-раскраски определяет, является ли он кратным совершенным кодом с заданными кратностью и радиусом.

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

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

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.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, если и 'только если

выполняется

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

j=0

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