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

• Автор: Пузынина, Светлана Александровна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Новосибирск
• Количество страниц: 79 с. : ил.

Глава 1. Периодичность совершенных раскрасок радиуса

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

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

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

Глава 2. Совершенные раскраски радиуса 1 вершин

графа 0(.£2) в три цвета

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

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

Приложение
Приложение

Глава 3. Периодичность совершенных раскрасок радиуса г >

бесконечной прямоугольной решетки
3.1. Конструкции и примеры
3.2. Периодичность
Глава 4. Периодичность центрированных функций
4.1. Бесконечная прямоугольная решетка
4.2. Примеры
4.3. Бесконечные треугольная и гексагональная решетки
4.4. Выводы
Приложение
Заключение
Список литературы

Объектом исследования настоящей диссертации являются проблемы алгебраической комбинаторики, теории кодирования и теории графов. Предмет исследования — совершенные раскраски, центрированные функции и другие обобщения совершенных кодов. Целью диссертации является исследование совершенных раскрасок и центрированных функций на бесконечных транзитивных решетках. Устанавливаются некоторые свойства этих объектов, в частности, исследован вопрос периодичности.
Раскраска вершин графа называется совершенной, если цветовой состав окружения каждой его вершины однозначно определяется цветом этой вершины. Понятие совершенной раскраски естественным образом возникает в теории графов и в алгебраической комбинаторике (дистанционнорегулярные графы) и в теории кодирования (совершенные коды). Ранее совершенные раскраски радиуса 1 изучались в различных контекстах и имели различные названия. В частности, в работах, близких к теории кодирования, такие раскраски назывались partition designs (схемы разбиения) [7] или equitable partitions (равномерные разбиения) [14]. Также использовались термины дистрибутивная [36] , isotropic coloring [4] и А-допустимая раскраска (где А - матрица параметров совершенной раскраски) [49], Данное понятие настолько естественно, что было введено независимо в нескольких работах.
Пусть G — (V, Е) — граф, А = (a,j) — квадратная матрица порядка п, г > 1. Рассмотрим раскраску графа G в го цветов и произвольную вершину х цвета i. Если количество вершин цвета j (отличных от ж) на расстоянии не более г от вершины х не зависит от выбора вершины х и равно Заметим, что любой граф G обладает совершенной раскраской, при которой все его вершины красятся в разные цвета, а если граф G регулярный

(то есть степени всех его вершин одинаковы), то для него существует совершенная раскраска в один цвет.
В теории кодирования совершенные раскраски (partition désignés) использовались в качестве инструмента для изучения кодов (см., например, [7]). Например, вершины цвета 1 совершенной раскраски радиуса 1 и-регустоянием 3. Приведенный пример показывает, что задача классификации совершенных раскрасок не может быть проще, чем задача классификации совершенных кодов, которая остается нерешенной уже несколько десятилетий. [39]
Понятие совершенной раскраски также связано с важными в теории кодирования понятиями полностью регулярного и равномерно упакованного кода (см., например, [37]). А именно, такие коды могут рассматриваться как совершенные раскраски гиперкуба в различное число цветов. Рассмотрим некоторый код С С Еп. Радиусом покрытия кода С называется такое минимальное число Д, что шары радиуса Л с центрами в кодовых вершинах покрывают весь гиперкуб. Предполагая, что радиус покрытия кода С равен Л, определим следующие множества: С* = {х Е Еп : р(х, С) — г},г = 0,1 Д. Двоичный код С называется полностью регулярным, если для всех г, г = 0,1 Л, произвольная вершина х е Сг- имеет фиксированное число <А соседей в множестве и фиксированное число щ соседей в множестве С+. Понятие полностью регулярного кода было введено Дель-сартом в 1973 году [9].
Понятие полностью регулярного кода очень близко к понятию равномерно упакованного кода [34]. Код С длины п с радиусом покрытия Л называется равномерно упакованным в широком смысле, если существуют числа такие что для всякой вершины и € Еп выполняется
гДе Ґк{у) — это число кодовых вершин на расстоянии к от V. Для кода С длины п с расстоянием с? введем множество У С Еп такое, что для любых у € К и а Є С расстояние с1(а, у) > е, где е = [^]. Если число векторов а из С таких, что е < Да, у) < е + 1, не зависит от выбора вектора у Є К, то
лярного графа с матрицей
образуют совершенный код с рас-

Матрицей совершенной раскраски ф является В = (6у)^_1} где = арг/! ЗЛЯ р (Е 1>ъ.

Рис. 3.1. Орбитные раскраски в два цвета.
Примеры.
1. Орбитные раскраски в два цвета. Существует 9 орбитных раскрасок в два цвета (см. Рис. 3.1). Эти раскраски содержатся в множестве совершенных раскрасок радиуса 1, которые были описаны Аксенович [1].
2. Трансляционные раскраски. Пусть Н' — группа трансляций, порожденная двумя неколлинеарными векторами и = («1, щ) и V = (гц, г^). Раскрасив каждую орбиту 71? под действием группы Н' в свой цвет, получим трансляционную раскраску. Эта раскраска совершенная любого радиуса в щУ2 — и2У1 цветов. Число цветов равно числу вершин в параллелограмме, натянутом на векторы и и V.
3. Совершенный код и раскраски, получаемые из него объединением цветов. Рассмотрим трансляционную раскраску, порожденную векторами (э—1-1, г) и (г, — г—1). Эта раскраска совершенная радиуса г вп = 2г2+2г+1

~о]Т

0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 1
1 0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 1 0
0 0 0 0 1 0 0 0 0

1 1 0 0 1 1 0 0 1
1 1 0 0 1 1 0 0 1
1 1 0 0 1 1 0 0 1
1 1 0 0 1 1 0 0 1
1 1 0 0 1 1 0 0 1
1 1 0 0 1 1 0 0 1

О О

1 1 0 0 1 1 0 0 1
1 1 0 0 1 1 0 0 1
0 0 1 1 0 0 1 1 0
0 0 1 1 0 0 1 1 0
1 1 0 0 1 1 0 0 1
1 1 0 0 1 1 0 0 1

1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1