Совершенные раскраски бесконечной прямоугольной решетки тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

ПУЗЫНИНА Светлана Александровна

СОВЕРШЕННЫЕ РАСКРАСКИ БЕСКОНЕЧНОЙ ПРЯМОУГОЛЬНОЙ РЕШЕТКИ

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

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

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

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

1111111111111111111»

ООЗ167313

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

Научные руководители Официальные оппоненты

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

кандидат физико-математических наук, С В Августинович доктор физико-математических наук, А В Кельманов,

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

Уральской государственный университет

Защита состоится "14" мая 2008 г в 17 часов на заседании диссертационного совета Д 003 015.01 в Институте математики им С. Л. Соболева СО РАН по адресу, пр Академика Коптюга, 4, 630090, г Новосибирск

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

Автореферат разослан "14" апреля 2008 г

Ученый секретарь диссертационного совета Д 003 015 01 при Институте математики имени С Л Соболева СО РАН

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

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

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

Рассмотрим произвольный граф G Раскраска вершин графа G называется совершенной радиуса г, если цветовой состав всякого шара радиуса г однозначно определяется цветом центра этого шара Числа atJ, задающие количество вершин цвета j в шаре с центром цвета г, определяют матрицу параметров совершенной раскраски Понятие совершенной раскраски естественным образом возникает в различных областях математики, поэтому оно было введено независимо в нескольких работах под разными названиями В частности, в работах, близких к теории кодирования, такие раскраски назывались partition designs (схемы разбиения) или equitable partitions (равномерные разбиения) Также использовались термины дистрибутивная, изотропная раскраска и А-допустимая раскраска, где А =

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

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

1 Работа выполнена при поддержке РФФИ (грант 07-01-00248) и Фонда содействия отечественной науке

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

Актуальность исследования совершенных раскрасок обусловлена также их связью со структурой групп автоморфизмов графов Основным способом построения совершенных раскрасок (в производных графах) является так называемый ор-битный метод, суть которого выражается в следующем факте Пусть (7 — произвольный обыкновенный граф с группой автоморфизмов Н и Н' — некоторая подгруппа группы Н Относительно Н' множество вершин графа О разбивается на орбиты Раскрашивая каждую из орбит своим цветом, получаем совершенную раскраску графа О О группе автоморфизмов графа можно сделать некоторые выводы по собственным значениям и собственным векторам графа, которые связаны с собственными значениями матрицы совершенной раскраски следующим образом характеристический многочлен матрицы параметров совершенной раскраски делит характеристический многочлен матрицы смежности графа В последнее время появляются публикации, в которых совершенные раскраски используются как инструмент в различных подходах к проблеме изоморфизма графов Проблема распознавания того, являются ли два конечных графа изоморфными, является одной из наиболее важных нерешенных проблем современной теории сложности вычислений Сложностной статус этой проблемы до сих пор не определен

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

метод Я-продолжаемых слов для доказательства периодичности двумерных слов и используется для доказательства периодичности совершенных раскрасок и центрированных функций Этот метод или его модификации могут быть использованы для решения различных вопросов о периодичности, которая является важным объектом исследования современной теории явыков Например, много усилий прилагается исследователями для проверки гипотезы Нива о связи комбинаторной сложности и периодичности

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

Цель работы состоит в исследовании свойств совершенных раскрасок, центрированных функций и других обобщений совершенных кодов на бесконечных транзитивных решетках

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

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

Апробация работы. Результаты работы докладывались на международных конференциях ALCOMA'05 (Algebraic Combinatorics and Applications) в Германии, CANT2006 (Combinatorics, Automata and Number Theory) в Бельгии, DM6 (6-я международная конференция "Дискретные модели в теории управляющих систем") в Москве, российской конференции ДАИО'04 (Дискретный Анализ и Исследование Операций) в Новосибирске, Шестой молодежной научной школе по дискретной математике и ее приложениям в 2007 году в Москве, международной конференции "Математика в современном мире" в Новосибирске в 2007 году Результаты докладывались на семинаре "Алгебраические системы" Уральского Государственного Университета, на семинаре Института Проблем Передачи Информации в Москве и семинарах "Теория кодирования", "Дискретный анализ", "Теория графов" и "Дискретно-экстремальные задачи" Института Математики СО РАН и Новосибирского Государственного Университета Результаты кандидатской диссертации были отмечены дипломами Всероссийского конкурса дипломных работ в 2003 и 2005 году, дипломами Международной Студенческой Научной Конференции, грантом "Лучшие аспиранты", грантом "Развитие научного потенциала высшей школы "(проект номер 82-87), стипендией Сибирско-Математи-ческого Журнала. Работа выполнена при поддержке РФФИ (грант 07-01-00248),

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

1 Доказано, что для любой совершенной раскраски радиуса 1 существует периодическая совершенная раскраска с теми же параметрами

2 Перечислены все допустимые матрицы совершенных раскрасок радиуса 1 в 3 цвета

3 Разработан метод доказательства периодичности двумерных слов с локальными условиями С помощью этого метода получены следующие результаты

3 1 Доказано, что всякая совершенная раскраска радиуса г > 1 графа G(I?) является периодической

3 2. Доказано, что любая ограниченная целочисленная цен-

трированная функция произвольного радиуса на 0(7?) является периодической Аналогичные результаты получены для бесконечной треугольной и гексагональной решеток

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

На защиту выносится совокупность результатов о свойствах совершенных раскрасок и центрированных функций на бесконечных транзитивных решетках

Публикации. По теме диссертации автором опубликованы работы [29]-[37]

Структура и объем работы. Работа состоит из введения, четырех глав, заключения, списка литературы из 49 наименований Общий объем работы — 79 страниц, включая 31 рисунок и 1 таблицу

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

Во введении даются необходимые определения, приводится краткий обзор полученных результатов Коротко излагается содержание диссертационной работы Основные понятия и определения даются в первой главе диссертации, некоторые вспомогательные определения и обозначения приведены в начале каждой главы Пусть О — (V, Е) — граф, А = (агз) — квадратная матрица порядка п, г > 1 Рассмотрим раскраску графа (7 в п цветов и произвольную вершину х цвета г Если количество вершин цвета з (отличных от х) на расстоянии не более г от вершины х не зависит от выбора вершины х и равно а13, то раскраска называется совершенной радиуса г с матрицей А Ранее совершенные раскраски изучались в различных контекстах и имели различные названия

Понятие совершенной раскраски является обобщением понятия совершенного кода Легко понять, что вершины цвета 1 совершенной раскраски регулярного графа степени п с матрицей ^ ^ и ^ 1 ^ образуют совершенный код с расстоянием 3

Понятие совершенной раскраски также связано с важными в теории кодирования понятиями полностью регулярного и равномерно упакованного кода А именно, такие коды могут рассматриваться как совершенные раскраски гиперкуба с подходящей матрицей параметров Понятие полностью регулярного кода было введено Дельсартом в 1973 году [7] Определение полностью регулярного кода может быть дано в терминах совершенных раскрасок Пусть С — некоторое подмножество вершин в п-мерном кубе Еп, рассмотрим дистанционную раскраску вершин гиперкуба относительно этого множества вершины из С красим в цвет 1, если расстояние от вершины х до ближайшей вершины из С равно г, то ж красится в цвет г + 1 Если дистанционная раскраска вершин гиперкуба относительно С является совершенной, то С является вполне регулярным кодом

Понятие вполне регулярного кода очень близко к понятию равномерно упакованного кода [26], а именно, равномерно упакованный код является вполне регулярным кодом, а вполне регулярный код является совершенной раскраской с трехдиа-гональной матрицей

Одним из известных примеров вполне регулярного кода является код Препараты (оптимальный код расстоянием 5) [15] Вершинами кода Препараты являются вершины цвета 1 совершенной раскраски радиуса 1 гиперкуба в 4 цвета Для длины п = 2т — 1 (при четном т > 2) соответствующая матрица име-/ О п 0 0 \

ет вид ф 2 п - 3 1 Вершины цветов 1 и 4 образуют

\ 0 0 п 0 / совершенный код, то есть если объединить цвета 1 и 4 в один цвет и 2 и 3 в другой, то получится матрица совершенной рас-

краски совершенного кода,

Понятие совершенной раскраски графа является весьма популярным объектом исследования в теории кодирования и криптографии До последнего времени список конструкций совершенных раскрасок гиперкуба в 2 цвета исчерпывался тривиальными сериями и одним спорадическим примером Таранни-кова в 6-й размерности Фон-дер-Флаасс рассматривает вопрос существования совершенных раскрасок в два цвета радиуса 1 гиперкубов с заданными параметрами Он доказал ряд необходимых условий на матрицу параметров совершенных раскрасок гиперкуба и построил рекурсивную конструкцию таких раскрасок, дающую бесконечную серию совершенных раскрасок, раскраски с ранее не встречавшимися параметрами, и, в частности, все множества параметров, для которых такие раскраски были ранее известны [27] Совершенные раскраски также имеют приложение в криптографии самое сильное необходимое условие существования совершенных раскрасок в булевом кубе получено с помощью новой оценки на корреляционную иммунность непостоянных несбалансированных булевых функций, установлена связь между корреляционно-иммунными функциями, достигающими новой границы корреляционной иммунности, и совершенными раскрасками [9] Полного описания всех матриц совершенных раскрасок гиперкуба пока не найдено даже для случая двух цветов

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

Совершенная раскраска графа тесно связана со структурой группы автоморфизмов графа Основным способом построения совершенных раскрасок (в производных графах) является так называемый орбитный метод, суть которого выражается в следующем факте (см , например, [28]) Пусть G — произвольный обыкновенный граф с группой автоморфизмов Н и Н' — некоторая подгруппа группы Н, Относительно Н' множество вершин графа G разбивается на орбиты Раскрашивая каждую из орбит своим цветом, получим совершенную раскраску графа G В [10], [11] Годсил использует совершенные раскраски (equitable partitions) для изучения схем отношений и групп автоморфизмов графов О группе автоморфизмов графа можно сделать некоторые выводы по собственным значениям и собственным векторам графа, которые связаны с собственными значениями матрицы совершенной раскраски следующим образом характеристический многочлен матрицы совершенной раскраски делит характеристический многочлен матрицы смежности графа [28]

Ранее изучались совершенные раскраски в два цвета некоторых графов и семейств графов n-мерного двоичного куба [27], графа бесконечной прямоугольной решетки [3], плоских триангуляций минимальной степени пять [19], графа Джонсона [25]

Голомб и Уэлш рассматривали совершенные коды в Zn [12] Они доказали, что для всякой длины п существуют совершенные коды, исправляющие одну ошибку, в метрике Ли Такие коды могут рассматриваться либо как регулярные периодические замощения евклидова пространства ¡К" сферами Ли радиуса 1 или как периодические замощения решетки Zn шарами радиуса 1 Также рассматривались совершенные коды радиусов больше 1 и были получены некоторые результаты о несуществовании таких кодов

Задача исследования центрированных функций и совершенных раскрасок на бесконечных транзитивных решетках также связана с теорией двумерных слов Центрированные функции и совершенные раскраски могут рассматриваться как двумерные

слова над конечным алфавитом слов и значений функции соответственно В диссертации вводится понятие R-продолжаемого слова и используется для доказательства периодичности центрированных функций и совершенных раскрасок Этот метод или его модификации могут быть использованы для изучения периодичности других двумерных слов Периодичность двумерных слов ранее уже изучалась Следующая гипотеза о связи комбинаторной сложности и периодичности известна как гипотеза Нива (Nivat's conjecture) [13] если существует пара целых чисел (n,m), такая что функция комбинаторной сложности pw(п, т) двумерного слова w удовлетворяет условию pw (п,т) < тп, то w имеет по крайней мере один вектор периодичности Слабые формы этой гипотезы для pw(n,m) < ran/144 и для pw(n,m) < тп/16 были доказаны в [8] и [16], соответственно

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

Основной результат этой главы сформулирован в теореме 1 , в которой утверждается, что для любой допустимой матрицы радиуса 1 существует периодическая совершенная раскраска Матрица называется допустимой, если существует совершенная раскраска бесконечной прямоугольной решетки с такой матрицей Для того, чтобы доказать эту теорему, предварительно доказываются восемь вспомогательных предложений (предложения 1-8) Кроме того, доказано, что периодическая раскраска может быть получена из непериодической специальными операциями, называемыми сдвигами бинарных диагоналей. Бинарная диагональ — это диагональ, состоящая из двух чередующихся цветов, под сдвигом бинарной диагонали подразумевается перестановка цветов внутри диагонали В случае существования непериодической совершенной раскраски с данной матрицей для этой матрицы существует бесконечное число (континуум) совершенных раскрасок Метод получения периодических раскрасок сдвигами бинарных диагоналей согласуется с известным в теории кодирования методом свитчинга, используемого для получения новых кодов из известных pa-

нее Основная идея метода свитчинга состоит в следующем в произвольном двоичном коде С длины п рассмотрим некоторое подмножество М кодовых слов. Если найдется в Еп подмножество М', отличное от множества М, причем множество С' = (С\М)иМ' является двоичным кодом с теми же параметрами, что и у кода С, то будем говорить, что код С получен из кода С свитчингом множества М, см. [18] Впервые свитчин-говый способ построения 1-совершенных кодов был предложен Васильевым [21] Далее свитчинговый метод разввался в работах Моллара, Августиновича и Соловьевой [1], [2], Малюгина [24], Кротова [23].

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

Граф бесконечной прямоугольной решетки является очень популярным объектом при изучении различных комбинаторных конструкций, в частности, упаковок, покрытий и замощений [17, 14] Довольно часто при этом возникают следующий вопрос если некоторая конструкция на графе (?(й2) существует, то следует ли отсюда существование конструкции с теми же параметрами, обладающей свойством периодичности7 Ответ на этот вопрос не всегда оказывается положительным Например, в работах [17] и [14] рассматривались замощения плоскости плитками Оказалось, что для некоторого набора плиток замощение существует, но все такие замощения оказываются непериодическими.

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

Ранее в [3] Аксенович перечислила все допустимые матрицы совершенных раскрасок радиуса 1 в 2 цвета Основным результатом второй главы диссертации является Теорема 2, в кото-

рой утверждается, что всякая совершенная раскраска радиуса 1 бесконечной плоской прямоугольной решетки в три цвета имеет одну из перечисленных в этой теореме матриц (с точностью до перестановки строк и столбцов, соответствующей некоторому переобозначению цветов) Таких матриц оказалось 21 Для каждой матрицы приведены примеры соответствующих раскрасок Матрица совершенной раскраски называется допустимой, если существует совершенная раскраска бесконечной прямоугольной решетки с этой матрицей Из 21 допустимой матрицы для пять матриц порождают непериодические совершенные раскраски

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

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

Доказано, что любая совершенная раскраска радиуса г > 1 является периодической (Теорема 3), в отличие от случая г = 1, в котором существуют также непериодические раскраски Получена верхняя граница на период, то есть по существу доказана конечность числа совершенных раскрасок фиксированного радиуса больше 1 Приведены некоторые конструкции и примеры совершенных раскрасок произвольных графов и графа бесконечной прямоугольной решетки Найден общий способ получения всех совершенных раскрасок бесконечной прямоугольной решетки заданного радиуса, большего 1, в заданное число цветов Для доказательства периодичности используется метод /¿-продолжаемых слов, который заключается в следующем Будем говорить, что двумерное слово ш является И-продолжаемым, если для любых х, ъ € 1? равенство Ивд(х) = Ивя(*) влечет ш\вя+1(х) = ы\ва+!(«) Здесь равенство Ибл(х) = Ивя(г) означает, что о>(х+у) = о>(г+у) для любых у, таких что ¡¡у|| < К Лемма 2 гласит, что если двумерное слово и над ко-

нечным алфавитом является Л-продолжаемым для некоторого Я > 0, то и) периодическое Таким образом, вместо периодичности можно доказывать Л-продолжаемость для некоторого Л, в некоторых случаях это оказывается удобным

Четвертая глава посвящена центрированным и квазицен-трированным функциям

Метод К-продолжаемых слов оказался полезным при доказательстве следующего результата любая ограниченная целочисленная центрированная функция любого радиуса на 0(Ъ2) является периодической (теорема 4) Функция на вершинах графа называется квазицентрированной радиуса г, если сумма ее значений по любой сфере радиуса г равна нулю Доказано, что квазицентрированные функции четного радиуса периодические, для нечетных радиусов существуют как периодические, так и непериодические квазицентрированные функции (теорема 5) В разделе 4 2 приведены конструкции непериодических центрированных функций радиуса 1 в G(Zn) (лемма 3) Аналогичные результаты получены для бесконечной треугольной и гексагональной решеток (теоремы б, 7, 8)

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

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

[1] Avgustiriovich S V , Solov'eva F I Construction of perfect binary codes by sequential translations of the i-components, Proc of Fifth Int Workshop on Algebraic and Comb Coding Theory Sozopol, Bulgaria June (1996) 9-14

[2] Avgustinovich S V , Solov'eva F I Construction of perfect binary codes by sequential translations of an «-components., // Problems of Inform TYansm 33 (3) (1997) 202-207

[3} Àxenovich M On multiple coverings of the infinite rectangular grid with balls of constant radius // Discrete Mathematics, 268 2003, p. 31-49

Brouwer A E A note on completely regular codes // Discrete mathematics, 1990, V 82, P 115-117

Berthe V , Vuillon L Tilings and rotations a two-dimensional generalization of Sturmian sequences // Discrete Math , 223 (2000),p 27-53

Camion P , Courteau B , Delsarte Ph On r-partition designs m Hamming spaces // Appl Algebra m Engrg , Comm Compt (AAECC). 1992 V. 2 P 147-162

Delsarte P An algebraic approach to the association schemes of coding theory // Philips Research Reports Supplements, Vol 10, 1973

Epifanio C , Koskas M , Mignosi F On a conjecture on bidimensional words // Theoretical Computer Science, v 299 n 1-3, p 123-150, 2003

Fon-Der-Flaass D G A bound on correlation immunity // Siberian Electronic Mathematical Reports 4 (2007) 133-135

Godsil C Equitable partitions // Combinatorics, Paul Erdos is Eighty Vol 1 Budapest , 1993 P 173-192

Godsil C D , Martin W J Quotients of association schemes //J Combm Theory Ser A 1995 V. 69, N 2 P 185-199

Golomb W , Welch L R Perfect codes m the Lee metric and the packing of polyommoes // SIAM J Appl Math 18 (1970) 302-317

Nivat M , Invited talk at ICALP'97

Penrose R The role of aethetics m pure and applied mathematical reserch //Bull Inst Math Appl 1974 V 10 P. 266-271

[15] Preparata F P A Class of optimum nonlinear double-error-correctmg codes // Inform and Control 1968 V 13, N 5 P 378-400

[16] Quas A , Zambom L Periodicity and local complexity // Theoretical Computer Science, v 319, Issue 1-3, p 229 - 240, 2004

[17] Robinson R Undecidabilty and nonperiodicity for tilings of the plane // Inventiones Math 1971 V 12 P 177-209

[18] Solov'eva F I On perfect codes and related topics // Com2Mac Lecture Note Series 13, Pohang 2004

[19] Августинович С В., Бородин О В , Фрид А Э Дистрибутивные раскраски плоских триангуляций минимальной степени 5 // Дискретный анализ и исследование операций 2001 Т 8, № 3 С 3-16

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

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

[22] Визинг В Г Дистрибутивная раскраска вершин графа // Дискрет анализ и исслед операций 1995 Т 2, № 4 С 3-12

[23] Кротов Д С Нижние границы на число m-квазигрупп порядка 4 и число совершенных двоичных кодов, // Дискр анализ и исслед опер , 1 (7) 2 (2000) 47-53

[24] Малюгин CAO нижней границе на число совершенных двочиных кодов // Дискр анализ и исслед опер , 1 (6) 4 (1999) 44-48

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

[26] Семаков Н В , Зайцев Г В , Зиновьев В А Равномерно упакованныхе коды // Проблемы передачи информации, том VII, Вып 1, 1971, стр 38-50

[27] Фон-Дер-Флаасс Д Г Совершенные 2-раскраски гиперкуба // Сиб мат журнал, 48-4 (2007), 923-930

[28] Цветкович Д , Дуб М , Захс X Спектры графов Киев, Наукова думка, 1984 С 121-138

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

[29] Puzynma S A Perfect colorings of the infinite rectangular grid // Bayreuther Mathematischen Schriften, Heft 74. 2005, p 317-331

[30] Puzynma S A , Avgustinovich S V On periodicity of two-dimensional words // CANT2006 EMS Summer School, International School and Conference on Combinatorics, Automata and Number Theory, Preproceedmgs

[31] Puzynma S A , Avgustinovich S V On periodicity of two-dimensional words, Theoretical Computer Science 391 (2008), p 178-187.

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

[33] Пузынина С А Периодичность совершенных раскрасок бесконечной прямоугольной решетки // Дискрет анализ и исслед операций Сер 1 2004 Т. 11, №1 С 79-92

[34] Пузынина С А Совершенные раскраски вершин графа G(Z2) в три цвета //Дискрет анализ и исслед операций Сер 2 2005 Т 12, Ш С 37-54

[35] Пузынина С А Совершенные раскраски бесконечной прямоугольной решетки Труды VI международной конференции "Дискретные модели в теории управляющих систем", 2004, с 209

[36] Puzynma S A On perfect colorings of the infinite rectangular grid Материалы российской конференции "Дискретный анализ и исследование операций", 2004, с 97

[37] Пузынина С А. Обзор по совершенным раскраскам и другим обобщениям совершенных кодов на бесконечных транзитивных решетках // Материалы международной конференции "Математика в современном мире", 2007, с 279280

Пузынина Светлана Александровна

Совершенные раскраски бесконечной прямоугольной решетки

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

Подписано в печать 02 04 2008 Формат 60x84 1/16 Уел печ л 1,1 Уч-изд л 1,0 Тираж 100 экз Заказ № 59

Отпечатано в ООО "Омега Принт" 630090 Новосибирск, пр Лаврентьева, 6

Введение.

Глава 1. Периодичность совершенных раскрасок радиуса бесконечной прямоугольной решетки

1.1. Определения и обозначения

1.2. Теорема о периодичности

Глава 2. Совершенные раскраски радиуса 1 вершин графа G(Z2) в три цвета

2.1. Необходимые условия допустимости матрицы

2.2. Теорема о раскрасках в три цвета

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

Раскраска вершин графа называется совершенной, если цветовой состав окружения каждой его вершины однозначно определяется цветом этой вершины. Понятие совершенной раскраски естественным образом возникает в теории графов и в алгебраической комбинаторике (дистанционно-регулярные графы) и в теории кодирования (совершенные коды). Ранее совершенные раскраски радиуса 1 изучались в различных контекстах и имели различные названия. В частности, в работах, близких к теории кодирования, такие раскраски назывались partition designs (схемы разбиения) [7] или equitable partitions [равномерные разбиения) [14]. Также использовались термины дистрибутивная [36] , isotropic coloring [4] и А-допустимая раскраска (где А - матрица параметров совершенной раскраски) [49]. Данное понятие настолько естественно, что было введено независимо в нескольких работах.

Пусть G = (V, Е) — граф, А = (о^) — квадратная матрица порядка п, г > 1. Рассмотрим раскраску графа G в-n цветов и произвольную вершину х цвета %. Если количество вершин цвета j (отличных от х) на расстоянии не более г от вершины х не зависит от выбора вершины х и равно а^, то раскраска называется совершенной радиуса г с матрицей А.

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

В теории кодирования совершенные раскраски (partition designee) использовались в качестве инструмента для изучения кодов (см., например, [7]). Например, вершины цвета 1 совершенной раскраски радиуса 1 п-регустоянием 3. Приведенный пример показывает, что задача классификации совершенных раскрасок не может быть проще, чем задача классификации совершенных кодов, которая остается нерешенной уже несколько десятилетий. [39]

Понятие совершенной раскраски также связано с важными в теории кодирования понятиями полностью регулярного и равномерно упакованного кода (см., например, [37]). А именно, такие коды могут рассматриваться как совершенные раскраски гиперкуба в различное число цветов. Рассмотрим некоторый код С С Еп. Радиусом покрытия кода С называется такое минимальное число R, что шары радиуса R с центрами в кодовых вершинах покрывают весь гиперкуб. Предполагая, что радиус покрытия кода С равен R, определим следующие множества: С{ = {х € Еп : р(х, С) = г},г = 0,1,.,Д. Двоичный код С называется полностью регулярным, если для всех г,г = 0,1,.,Л, произвольная вершина х G Q имеет фиксированное число di соседей в множестве С{ и фиксированное число щ соседей в множестве Сг-+1. Понятие полностью регулярного кода было введено Дель-сартом в 1973 году [9].

Понятие полностью регулярного кода очень близко к понятию равномерно упакованного кода [34]. Код С длины п с радиусом покрытия R называется равномерно упакованным в широком смысле, если существуют числа ах,., ап, такие что для всякой вершины v £ Еп выполняется где fk{v) — это число кодовых вершин на расстоянии к от v. Для кода С длины п с расстоянием d введем множество Y С Еп такое, что для любых у еУ и а в С расстояние d(a, у) > е, где е = Если число векторов а из С таких, что е < d(a, у) < е +1, не зависит от выбора вектора у G У, то лярного графа с матрицей образуют совершенный код с расп соответствующая матрица имеет вид: Вершины цветов 1 такой код называется равномерно упакованным в узком смысле [45]. Ясно, что равномерно упакованный код в узком смысле является полностью регулярным кодом, а полностью регулярный код является совершенной раскраской с трехдиагональной матрицей. Определение полностью регулярного кода можно также дать в терминах совершенных раскрасок. Пусть С — некоторое подмножество Еп, рассмотрим дистанционную раскраску вершин гиперкуба-относительно этого множества: вершины из С красим в цвет 1, если расстояние от вершины х до ближайшей вершины из С равно г, то ж красится в цвет г + 1. Если дистанционная раскраска вершин гиперкуба относительно С является совершенной, то С является полностью регулярным кодом.

Одним из известных примеров полностью регулярного кода является код Препараты (оптимальный код расстоянием 5) [22]. Кодовыми вершинами кода Препараты являются вершины цвета 1 совершенной раскраски радиуса 1 гиперкуба в 4 цвета. Для длины п = 2Ш — 1 (при четном га > 2) о п о о \ 1 о п — 1 о О 2' п — 3 1 \ 0 0 п О и 4 образуют совершенный код, то есть если объединить цвета 1 и 4 в один цвет и 2 и 3 в другой, то получится матрица совершенной раскраски совершенного кода (см. Глава 3, лемма 1).

Совершенные раскраски тесно связаны со структурой групп автоморфизмов графов. Основным способом построения совершенных раскрасок является так называемый орбитный метод, суть которого выражается в следующем факте (см., например [49]). Пусть G — произвольный граф с группой автоморфизмов Н и Н' — некоторая подгруппа группы Н. Относительно Н' множество вершин графа G разбивается на орбиты. Раскрашивая, каждую из орбит своим цветом, получаем совершенную раскраску графа G.

В [14], [15] Годсил использует совершенные раскраски (equitable partitions) для изучения схем отношений и групп автоморфизмов графов. О группе автоморфизмов графа можно сделать некоторые выводы по собственным значениям и собственным векторам графа, которые связаны с собственными значениями матрицы совершенной раскраски следующим образом: характеристический многочлен матрицы совершенной раскраски делит характеристический многочлен матрицы смежности графа [49].

В последнее время появляются публикации, в которых совершенные раскраски используются как инструмент в различных подходах к проблеме изоморфизма графов (см., например, [12]). Проблема распознавания того, являются ли два конечных графа изоморфными, является одной из наиболее важных нерешенных проблем современной теории сложности вычислений. Сложностной статус этой проблемы до сих пор не определен. В статье [36] Визинг рассматривает связь совершенных раскрасок (дистрибутивных раскрасок) с проблемой изоморфизма графов. В статье также излагается полиномиальный алгоритм раскраски произвольного обыкновенного графа в минимальное число цветов.

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

Ранее изучались совершенные раскраски в два цвета некоторых графов и семейств графов: n-мерного двоичного куба [47], графа бесконечной прямоугольной решетки [4], плоских триангуляций минимальной степени пять [30], графа Джонсона [41], [19].

Понятие совершенной раскраски графа является весьма популярным объектом исследования в теории кодирования и криптографии. До последнего времени список конструкций совершенных раскрасок гиперкуба в 2 цвета исчерпывался тривиальными сериями и одним спорадическим примером Таранникова в 6-й размерности. Фон-дер-Флаасс рассматривает вопрос существования совершенных раскрасок в два цвета радиуса 1 гиперкубов с заданными параметрами. Он получил ряд необходимых условий на матрицу параметров совершенных раскрасок гиперкуба и построил рекурсивную конструкцию таких раскрасок, дающую бесконечную серию совершенных раскрасок, раскраски с ранее не встречавшимися параметрами, и, в частности, все множества параметров, для которых такие раскраски были ранее известны [47].

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

В работе [30] описаны все матрицы совершенных раскрасок графов плоских триангуляций минимальной степени пять.

Также изучались совершенные раскраски в два цвета графа Джонсона J(n, w), вершинами которого является все вектора из гиперкуба Еп веса w, две вершины смежны, если расстояние Хэмминга между ними равно 2 [41], [19]. Задача описания матриц совершенных раскрасок полностью решена для п < 8, найдены конструкции1 серий раскрасок для произвольных п; рассматривалось свойство ^-регулярности совершенных раскрасок. Совершенная раскраска графа Джонсона J(n,w) называется ^-регулярной, если существует такой набор чисел 7jj, -что для любых двух векторов х,у 6 Еп, таких, что wt(x) = г, wt(y) = j, у ■< х, г < к ^ w выполняется |r^nW| = 7ij, где W-множество белых вершин, Тух - грань, соответствующая паре векторов х, у из Еп, т. е. множество {z + y — x : z 6 Еп, х z}. Ранее подобные вопросы на таких графах изучались для полностью регулярных [18] и совершенных кодов [11], которые являются частными случаями совершенных раскрасок.

В [4] Аксенович рассматривала совершенные раскраски произвольного радиуса бесконечной плоской прямоугольной решетки в два цвета. В статье было выделено два типа совершенных раскрасок, определяемых цветовым окружением вершины на расстоянии 1. Совершенная раскраска называется раскраской типа А, если некоторая вершина имеет нечетное число смежных с ней вершин каждого цвета или вершины одного цвета по горизонтали и вертикали. Совершенная раскраска называется раскраской типа В в противном случае. Все раскраски типа В описаны, они имеют диагональный вид. Для раскрасок типа А получены условия на параметры матрицы: доказано, что для раскрасок такого типа выполняется \ац 4-1 — а,2\\ <4.

Голомб и Уэлш рассматривали совершенные коды в Ъп [16], [17]. Они доказали, что для всякой длины п существуют совершенные коды, исправляющие одну ошибку, в метрике- Ли. Такие коды могут рассматриваться либо как регулярные периодические замощения евклидова пространства Мп сферами Ли радиуса 1 или как периодические замощения решетки I/1 шарами радиуса 1. Также рассматривались совершенные коды радиусов больше 1 и были получены некоторые результаты о несуществовании таких кодов.

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

Центрированные функции на бесконечной прямоугольной решетке также связаны с дискретным аналогом известной в интегральной геометрии проблемы Помпейю [33].

Проблема Помпейю может быть сформулирована следующим образом: если известны значения интегралов от функции на инвариантном относительно группового действия семействе множеств, можно ли однозначно определить функцию? В двумерном случае нужно описать все такие области ficl2, что для любой функции / из равенств нулю интегралов f(x,y)dxdy = О J тпО, m пробегает всю группу М(2) движений плоскости) следует, что /(ж, у) =

О почти всюду.

-«

В работе рассматривается дискретный аналог проблемы Помпейю.

Пусть S — семейство конечных подмножеств Zn, А — группа трансляций на Ъп. Задача состоит в том, чтобы дать необходимые и достаточные условия на семейство S для того чтобы

О) = 0 для всех Ае A, S eS ^ f = 0. xe\(S)

В [29] получен следующий результат. Обозначим zs = z^1 Ps{z) — ^se5zs. Доказано, что SxgA(S) f(x) ~ 0 для всех Л € Л, S € S влечет / = 0 тогда и только тогда, когда многочлены {Р5; S £ <S} не имеют общих нулей в Сп. Из этого следует, в частности, решение проблемы трех квадратов: пусть в 1? семейство S состоит из трех квадратов со сторонами М, N и К. Тогда / = 0 тогда и только тогда, когда М + 1, N + 1 и if + 1 попарно взаимно просты.

Мы рассматриваем случай, когда S состоит из одной конечной области Р. Функцию / : Ъп —> % назовем Р-распределепной, если для любого у eZn выполняется

J2f(x + y) = Ох&Р

В случае, когда Р — шар радиуса г, jP-распределенная функция является центрированной радиуса г. В случае, когда Р — сфера радиуса г, Р-распределенная функция является квазицентрированной радиуса г.

Понятие центрированной функции было введено как обобщение понятия совершенного кода. Если / : И1 —> {0,1} — 1-центрированная функция радиуса г, то вершины, в которых функция принимает значение 1, образуют совершенный код с расстоянием 2r + 1.

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

Периодичность двумерных слов ранее уже изучалась. Следующая гипотеза о связи комбинаторной сложности и периодичности известна как гипотеза Нива (Nivat's conjecture) [20]: если существует пара целых чисел (n, т), такая что функция комбинаторной сложности pw{n,m) двумерного слова w удовлетворяет условию pw (п, т) < тп, то w имеет по крайней мере вектор периодичности. Слабые формы этой гипотезы для pw(n,m) < mn/144 и для pw(n,m) < тп/16 были доказаны were С. Epifanio, М. Koskas, F. Mignosi в [10] и A. Quas, L. Zamboni в [26], соответственно. В [5] V. Berthe, L. Vuillon исследовали понятие минимальной сложности для двумерных последовательностей, в частности, они привели пример двумерной последовательности с комбинаторной сложностью pw(n, т) = тп+т для произвольных целых чисел (m,n), которая равномерно рекуррентна и не имеет рационального вектора периодичности.

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

Первая глава диссертации посвящена периодичности совершенных раскрасок радиуса 1 плоской бесконечной прямоугольной решетки. Основной результат результат этой главы сформулирован в теореме 1, в которой утверждается, что для любой допустимой матрицы радиуса 1 существует периодическая совершенная раскраска. Матрица называется допустимой, если существует совершенная раскраска бесконечной прямоугольной решетки с такой матрицей. Для того, чтобы доказать эту теорему, предварительно доказываются восемь вспомогательных предложений (предложения 1-8). Кроме того, доказано, что периодическая раскраска может быть получена из непериодической специальными операциями, называемыми сдвигами бинарных диагоналей. Бинарная диагональ — это диагональ, состоящая из двух чередующихся цветов, под сдвигом бинарной диагонали подразумевается перестановка цветов внутри диагонали. В случае существования непериодической совершенной раскраски с данной матрицей для этой матрицы существует бесконечное число (континуум) совершенных раскрасок. Метод получения периодических раскрасок сдвигами бинарных диагоналей согласуется с известным в теории кодирования методом свитчинга получения новых кодов из известных ранее. Основная идея метода свитчинга состоит в следующем: в произвольном двоичном коде С длины п рассмотрим некоторое подмножество М кодовых слов. Если найдется в Еп подмножество М', отличное от множества М, и множество С' — (С \ М) U М' является двоичным кодом с параметрами, совпадающими с параметрами кода С, то говорят, что код С' получен из кода С свитчингом множества М на множество М' [28]. Впервые свитчинговый способ построения кодов был предложен Ю. Л. Васильевым [35]. Далее свитчинговый метод развивался в работах Моллара, Августиновича и Соловьевой [1], [2], Малюгина [40], Кротова [38]. С помощью этого подхода была решена серия проблем, касающихся структуры совершенных кодов: например, обнаружены совершенные коды с тривиальной группой автоморфизмов, доказано существование несистематических совершенных кодов, кодов полного ранга.

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

Вторая глава диссертации посвящена описанию параметров совершенных раскрасок бесконечной прямоугольной решетки в три цвета. Ранее в [4] Аксенович перечислила все допустимые матрицы совершенных раскрасок радиуса 1 в 2 цвета. Основным результатом второй главы диссертации является Теорема 2, в которой утверждается, что всякая совершенная раскраска радиуса 1 бесконечной плоской прямоугольной решетки в три цвета имеет одну из 21 матриц, перечисленных в этой теореме (с точностью до перестановки строк и столбцов, соответствующей некоторому переобозначению цветов). Для каждой матрицы приведены примеры соответствующих раскрасок. Матрица совершенной раскраски называется допустимой, если существует совершенная раскраска бесконечной прямоугольной решетки для соответствующего радиуса. Из 21 допустимой матрицы для пяти матриц существуют непериодические совершенные раскраски.

Для доказательства Теоремы 2 было доказано 12 предложений о необходимых условиях допустимости матрицы (Предложения 10-21), которые имеют самостоятельную ценность, так как выполняются для произвольного числа цветов, а некоторые не только для бесконечной прямоугольной решетки, но и для произвольных графов или широких классов графов.

Третья глава посвящена совершенным раскраскам на бесконечной прямоугольной решетке. Доказано, что любая совершенная раскраска радиуса г > 1 является периодической, в отличие от случая г = 1, в котором существуют также непериодические раскраски. Получена верхняя граница на период, то есть по существу доказана конечность числа совершенных раскрасок радиуса больше 1. Приведены некоторые конструкции и примеры совершенных раскрасок произвольных графов и графа бесконечной прямоугольной решетки. Найден общий способ получения всех совершенных раскрасок бесконечной прямоугольной решетки заданного радиуса, большего 1, в заданное число цветов. Для доказательства периодичности используется метод Д-продолжаемых слов, который заключается в следующем. Будем говорить, что двумерное слово ш является R-продолжаемым, если для любых х, z е Z2 равенство о>|£д(х) = Чвл(а) влечет Иб^х) = Иbr+1(z)-Обозначение Ивя(х) = H-Br(z) означает, что а;(х+у) = a;(z + y) для любых у, таких что |]у)| < R. Лемма 2 гласит, что если двумерное слово а; над конечным алфавитом является ^-продолжаемым для некоторого R > 0, то о; периодическое. Таким образом, вместо периодичности можно доказывать ^-продолжаемость для некоторого R; в некоторых случаях это оказывается удобным.

Этот же метод оказался полезным при доказательстве следующего результата: любая ограниченная целочисленная центрированная функция любого радиуса на G(Z2) является периодической (теорема 4). Центрированным и квазицентрированным функциям посвящена четвертая глава. Доказано, что квазицентрированные функции четного радиуса периодические, для нечетных радиусов существуют как периодические, так и непериодические квазицентрированные функции (теорема 5). В разделе 4.2 приведены конструкции непериодических центрированных функций радиуса 1 в G(Zn) (лемма 3). Аналогичные результаты получены для бесконечной треугольной и гексагональной решеток (теоремы б, 7, 8).

Результаты работы опубликованы и докладывались на международных конференциях АЬСОМА'Об (Algebraic Combinatorics and Applications) в Германии, CANT2006 (Combinatorics, Automata and Number Theory) в Бельгии, DM6 (6-я международная конференция "Дискретные модели в теории управляющих систем") в 2004 году в Москве, российских конференциях DAOR'04 (Дискретный Анализ и Исследование Операций) в Новосибирске, Шестой молодежной научной школе по дискретной математике и ее приложениям в 2007 г. в Москве, на конференции "Математика в современном мире"в Новосибирске в 2007 году. Результаты докладывались на семинаре "Алгебраические системы" Уральского Государственного Университета, на научном семинаре Института Проблем Передачи Информации им. А.А. Харкевича в Москве, на семинарах "Теория кодирования", "Дискретный анализ" и "Теория графов" Новосибирского Государственного Университета и Института Математики.

Автор выражает глубокую признательность и благодарность научному руководителю Августиновичу С.В. и всем сотрудникам ВТК "Совершенные структуры" за помощь, постоянное внимание и всестороннюю поддержку.

4.4 Выводы

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

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

Заключение

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

Установлены некоторые необходимые условия на матрицу параметров совершенной раскраски, перечислены все матрицы совершенных раскрасок радиуса 1 в 3 цвета.

1 В диссертации представлен метод Д-продолжаемых слов доказательства периодичности двумерных слов с локальными условиями. Этот метод ис1 пользован для исследования периодичности центрированных функций и совершенных раскрасок.

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

Доказано, что любая ограниченная центрированная функция любого радиуса на G(l?) является периодической. Доказано, что любая ограниченная квазицентрированная функция нечетного радиуса на G(Z2) является периодической, существуют непериодические квазицентрированные функции нечетного радиуса. Аналогичные результаты получены для бесконечной треугольной и гексагональной решеток.

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

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

1. Avgustinovich S. V., Solov'eva F. 1. Construction of perfect binary codes by sequential translations of the i-components, Proc. of Fifth Int. Workshop on Algebraic and Comb. Coding Theory. Sozopol, Bulgaria. June (1996) 9-14.

2. Avgustinovich S. V., Solov'eva F. I. Construction of perfect binary codes by sequential translations of an cc-components, // Problems of Inform. Transm. 33 (3) (1997) 202-207.

3. Avgustinovich S. V., Mogilnykh I. Yu. On perfect colorings of Johnson graph in two colors// Proceedings XI International symposium on Problems of Redundancy in Information and Control Systems pp. 205208.

4. Axenovich M. On multiple coverings of the infinite rectangular grid with balls of constant radius. // Discrete Mathematics, 268 (2003), P. 31-49.

5. Berthe V., Vuilion L. Tilings and rotations: a two-dimensional generalization of Sturmian sequences // Discrete Math., 223 (2000), p. 27-53.

6. Brouwer A. E. A note on completely regular codes. // Discrete mathematics, 1990, V. 82, P. 115-117.

7. Camion P., Courteau B,, Delsarte Ph. On r-partition designs in Hamming spaces // Appl. Algebra in Engrg., Comm. Compt. (AAECC). 1992. V. 2. P. 147-162.

8. Costa S. I. R., Muniz M., Agustini E., Palazzo R. Graphs, tessellations, and perfect codes on flat tori // Information Theory, IEEE Transactions on Volume 50, Issue 10, Oct. 2004 Page(s): 2363 2377

9. Delsarte P. An algebraic approach to the association schemes of coding theory // Philips Research Reports Supplements, Vol. 10, 1973.

10. Epifanio C., Koskas M., Mignosi F. On a conjecture on bidimensional words // Theoretical Computer Science, v.299 n.1-3, p.123-150, 2003.

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

12. Fiala J., Paulusma D. and Telle J.A. Locally constrained graph homomorphisms and equitable partitions //to appear in European Journal of Combinatorics in April, 2008.

13. Fon-Der-FIaass D. G. A bound on correlation immunity // Siberian Electronic Mathematical Reports 4 (2007) 133-135.

14. Godsil C. Equitable partitions. // Combinatorics, Paul Erdos is Eighty Vol. 1. Budapest , 1993. P. 173-192.

15. Godsil C. D., Martin W. J. Quotients of association schemes // J. Combin. Theory. Ser. A. 1995. V. 69, N 2. P. 185-199.

16. Golomb W., Welch L. R. Perfect codes in the Lee metric and the packing of polyominoes // SIAM J. Appl. Math. 18 (1970) 302-317.

17. Golomb S. W., Welch L. R. Algebraic coding and the Lee metric, // Proc. Sympos. Math. Res. Center, Madison, Wis., (1968) pp 175-194, John Wiley, New York.

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

19. Mogilnykh I. Yu. On k-regularity of perfect colorings of Johnson graph in two colors // Proc. Tenth Int. Workshop on Algebraic and Combinatorial Coding Theory, pp. 198-201, 2006.

20. Nivat M., Invited talk at ICALP'97.

21. Penrose R. The role of aethetics in pure and applied mathematical reserch. // Bull. Inst. Math. Appl. 1974. V. 10. P. 266-271.

22. Preparata F. P. A Class of optimum nonlinear double-error-correcting codes // Inform, and Control. 1968. V. 13, N 5. P. 378-400.

23. Puzynina S. A. Perfect colorings of the infinite rectangular grid // Bayreuther Mathematischen Schriften, Heft 74, 2005, p. 317-331.

24. Puzynina S. A., Avgustinovich S. V. On periodicity of two-dimensional words // CANT2006: EMS Summer School, International School and Conference on Combinatorics, Automata and Number Theory, Preproceedings.

25. Puzynina S. A., Avgustinovich S. V. On periodicity of two-dimensional words // Theoretical Computer Science 391 (2008), p. 178187.

26. Quas A., Zamboni L. Periodicity and local complexity // Theoretical Computer Science, v. 319, Issue 1-3, p. 229-240, 2004.

27. Robinson R. Undecidabilty and nonperiodicity for tilings of the plane. // Inventiones Math. 1971. V. 12. P. 177-209.

28. Solov'eva F. I. On perfect codes and related topics // Com2Mac Lecture Note Series 13, Pohang 2004.

29. Zeilberger D. The Pompeiu problem for discrete space // Proc. Natl. Acad. Sci. 75, 3555-3556 (1978).

30. Августинович С. В., Бородин О. В., Фрид А. Э. Дистрибутивные раскраски плоских триангуляций минимальной степени 5. // Дискретный анализ и исследование операций. 2001. Т.8, № 3. С. 3-16.

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

32. Августинович С. В. Комбинаторные и метрические свойства совершенных кодов и раскрасок // кандидатская диссертация.

33. Аграновский М. JI. О возмущениях спектра в проблеме Помпейю // Сборник научных трудов, Новосибирск, 1990, с. 47-58.

34. Бассалыго JI. А., Зайцев Г. В., Зиновьев В. А. О равномерно упакованных кодах // Проблемы передачи информации, том X, Вып.1, 1994, стр. 9-14.

35. Васильев Ю. Л. О негрупповых кодах // Проблемы кибернетики. М, Наука, 1962. Вып. 8. С. 337-339.

36. Визинг В. Г. Дистрибутивная раскраска вершин графа // Дискрет, анализ и исслед. операций. 1995. Т. 2, № 4. С. 3-12.

37. Зиновьев В. А,, Рифа Дж. О новых полностью регулярных q-ичных кодах. // Проблемы передачи информации. 2007. Т. 43, Вып. 2. С. 34-51.

38. Кротов Д. С. Нижние границы на число m-квазигрупп порядка 4 и число совершенных двоичных кодов, ]/ Дискр. анализ и исслед. опер., 1 (7) 2 (2000) 47-53.

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

40. Малюгин С. А. О нижней границе на число совершенных двочиных кодов, // Дискр. анализ и исслед. опер., 1 (6) 4 (1999) 44-48.

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

42. Пузынина С. А. Периодичность совершенных раскрасок бесконечной прямоугольной решетки // Дискрет, анализ и исслед. операций. Сер. 1. 2004 Т. 11, т. С. 79-92.

43. Пузынина С. А. Совершенные раскраски вершин графа G(Z2) в три цвета. //Дискрет, анализ и исслед. операций. Сер. 2. 2005 Т. 12, №1. С. 37-54.

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

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

46. Фон-Дер-Флаасс Д. Г. Совершенные 2-раскраски гиперкуба. // Сиб. мат. журнал, 48:4 (2007), 923-930.

47. Харари Ф. Теория графов. М: Мир, 1973.

48. Цветкович Д., Дуб М., Захс X. Спектры графов. Киев, Наукова думка, 1984. С. 121-138.