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

РОССИЙСКАЯ АКАДЕМИЯ НАУК

СИБИРСКОЕ ОТДЕЛЕНИЕ

ИНСТИТУТ МАТЕМАТИКИ им. С.Л. СОБОЛЕВА

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

УДК 519.1

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

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

решетки

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

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

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

к.ф.-м.н.

С.В. Августинович Новосибирск 2008

ОГЛАВЛЕНИЕ

стр.

Введение............................................................... Глава 1. Периодичность совершенных раскрасок радиуса бесконечной прямоугольной решетки.................. 1.1. Определения и обозначения................................... 1.2. Теорема о периодичности...................................... Глава 2. Совершенные раскраски радиуса 1 вершин графа G(Z 2 ) в три цвета.................................. 2.1. Необходимые условия допустимости матрицы................. 2.2. Теорема о раскрасках в три цвета............................. Приложение 1...................................................... Приложение 2...................................................... Глава 3. Периодичность совершенных раскрасок радиуса r > бесконечной прямоугольной решетки.................. 3.1. Конструкции и примеры....................................... 3.2. Периодичность................................................. Глава 4. Периодичность центрированных функций........... 4.1. Бесконечная прямоугольная решетка.......................... 4.2. Примеры....................................................... 4.3. Бесконечные треугольная и гексагональная решетки......... 4.4. Выводы........................................................ Приложение 3...................................................... Заключение........................................................... Список литературы................................................. Введение Объектом исследования настоящей диссертации являются проблемы алгебраической комбинаторики, теории кодирования и теории графов. Предмет исследования совершенные раскраски, центрированные функции и другие обобщения совершенных кодов. Целью диссертации является исследование совершенных раскрасок и центрированных функций на бесконечных транзитивных решетках. Устанавливаются некоторые свойства этих объектов, в частности, исследован вопрос периодичности.

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

Пусть G = (V, E) граф, A = (aij ) квадратная матрица порядка n, r 1. Рассмотрим раскраску графа G в n цветов и произвольную вершину x цвета i. Если количество вершин цвета j (отличных от x) на расстоянии не более r от вершины x не зависит от выбора вершины x и равно aij, то раскраска называется совершенной радиуса r с матрицей A.

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

В теории кодирования совершенные раскраски (partition designes) использовались в качестве инструмента для изучения кодов (см., например, [7]). Например, вершины цвета 1 совершенной раскраски радиуса 1 n-регуn лярного графа с матрицей образуют совершенный код с расn стоянием 3. Приведенный пример показывает, что задача классификации совершенных раскрасок не может быть проще, чем задача классификации совершенных кодов, которая остается нерешенной уже несколько десятилетий. [39] Понятие совершенной раскраски также связано с важными в теории кодирования понятиями полностью регулярного и равномерно упакованного кода (см., например, [37]). А именно, такие коды могут рассматриваться как совершенные раскраски гиперкуба в различное число цветов. Рассмотрим некоторый код C E n. Радиусом покрытия кода C называется такое минимальное число R, что шары радиуса R с центрами в кодовых вершинах покрывают весь гиперкуб. Предполагая, что радиус покрытия кода C равен R, определим следующие множества: Ci = {x E n : (x, C) = i}, i = 0, 1,..., R. Двоичный код C называется полностью регулярным, если для всех i, i = 0, 1,..., R, произвольная вершина x Ci имеет фиксированное число di соседей в множестве Ci и фиксированное число ui соседей в множестве Ci+1. Понятие полностью регулярного кода было введено Дельсартом в 1973 году [9].

Понятие полностью регулярного кода очень близко к понятию равномерно упакованного кода [34]. Код C длины n с радиусом покрытия R называется равномерно упакованным в широком смысле, если существуют числа 1,..., n, такие что для всякой вершины v E n выполняется где fk (v) это число кодовых вершин на расстоянии k от v. Для кода C длины n с расстоянием d введем множество Y E n такое, что для любых y Y и a C расстояние d(a, y) e, где e = [ d1 ]. Если число векторов a из C таких, что e d(a, y) e + 1, не зависит от выбора вектора y Y, то такой код называется равномерно упакованным в узком смысле [45]. Ясно, что равномерно упакованный код в узком смысле является полностью регулярным кодом, а полностью регулярный код является совершенной раскраской с трехдиагональной матрицей. Определение полностью регулярного кода можно также дать в терминах совершенных раскрасок. Пусть некоторое подмножество E n, рассмотрим дистанционную раскраску вершин гиперкуба относительно этого множества: вершины из C красим в цвет 1, если расстояние от вершины x до ближайшей вершины из C равно i, то x красится в цвет i + 1. Если дистанционная раскраска вершин гиперкуба относительно C является совершенной, то C является полностью регулярным кодом.

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

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

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

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

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

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

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

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

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

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

Также изучались совершенные раскраски в два цвета графа Джонсона J(n, w), вершинами которого является все вектора из гиперкуба E n веса w, две вершины смежны, если расстояние Хэмминга между ними равно 2 [41], [19]. Задача описания матриц совершенных раскрасок полностью решена для n 8, найдены конструкции серий раскрасок для произвольных n;

рассматривалось свойство k-регулярности совершенных раскрасок. Совершенная раскраска графа Джонсона J(n, w) называется k-регулярной, если существует такой набор чисел ij, что для любых двух векторов x, y E n, таких, что wt(x) = i, wt(y) = j, y x, i k w выполняется |y W | = x ij, где W-множество белых вершин, x - грань, соответствующая паре векторов x, y из E n, т. е. множество {z +y x : z E n, x z}. Ранее подобные вопросы на таких графах изучались для полностью регулярных [18] и совершенных кодов [11], которые являются частными случаями совершенных раскрасок.

В [4] Аксенович рассматривала совершенные раскраски произвольного радиуса бесконечной плоской прямоугольной решетки в два цвета. В статье было выделено два типа совершенных раскрасок, определяемых цветовым окружением вершины на расстоянии 1. Совершенная раскраска называется раскраской типа A, если некоторая вершина имеет нечетное число смежных с ней вершин каждого цвета или вершины одного цвета по горизонтали и вертикали. Совершенная раскраска называется раскраской типа B в противном случае. Все раскраски типа B описаны, они имеют диагональный вид. Для раскрасок типа А получены условия на параметры матрицы: доказано, что для раскрасок такого типа выполняется |a11 + 1 a21 | 4.

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

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

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

Проблема Помпейю может быть сформулирована следующим образом:

если известны значения интегралов от функции на инвариантном относительно группового действия семействе множеств, можно ли однозначно определить функцию? В двумерном случае нужно описать все такие области R2, что для любой функции f из равенств нулю интегралов (m пробегает всю группу M (2) движений плоскости) следует, что f (x, y) = 0 почти всюду.

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

семейство конечных подмножеств Zn, группа трансляПусть S ций на Zn. Задача состоит в том, чтобы дать необходимые и достаточные условия на семейство S для того чтобы В [29] получен следующий результат. Обозначим zs = z11...znn, PS (z) = sS z. Доказано, что x(S) f (x) = 0 для всех, S S влечет f 0 тогда и только тогда, когда многочлены {PS ; S S} не имеют общих нулей в Cn. Из этого следует, в частности, решение проблемы трех квадратов: пусть в Z2 семейство S состоит из трех квадратов со сторонами M, N и K. Тогда f 0 тогда и только тогда, когда M + 1, N + 1 и K + попарно взаимно просты.

Мы рассматриваем случай, когда S состоит из одной конечной области P. Функцию f : Zn Z назовем P -распределенной, если для любого y Zn выполняется В случае, когда P шар радиуса r, P -распределенная функция является центрированной радиуса r. В случае, когда P сфера радиуса r, P -распределенная функция является квазицентрированной радиуса r.

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

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

Периодичность двумерных слов ранее уже изучалась. Следующая гипотеза о связи комбинаторной сложности и периодичности известна как гипотеза Нива (Nivat’s conjecture) [20]: если существует пара целых чисел (n, m), такая что функция комбинаторной сложности pw (n, m) двумерного слова w удовлетворяет условию pw (n, m) mn, то w имеет по крайней мере вектор периодичности. Слабые формы этой гипотезы для pw (n, m) mn/ и для pw (n, m) mn/16 были доказаны were C. Epifanio, M. Koskas, F.

Mignosi в [10] и A. Quas, L. Zamboni в [26], соответственно. В [5] V. Berthe, L. Vuillon исследовали понятие минимальной сложности для двумерных последовательностей, в частности, они привели пример двумерной последовательности с комбинаторной сложностью pw (n, m) = mn+m для произвольных целых чисел (m, n), которая равномерно рекуррентна и не имеет рационального вектора периодичности.

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

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

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

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

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

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

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

Будем говорить, что двумерное слово является R-продолжаемым, если для любых x, z Z2 равенство |BR (x) = |BR (z) влечет |BR+1 (x) = |BR+1 (z).

Обозначение |BR (x) = |BR (z) означает, что (x + y) = (z + y) для любых y, таких что y R. Лемма 2 гласит, что если двумерное слово над конечным алфавитом является R-продолжаемым для некоторого R 0, то периодическое. Таким образом, вместо периодичности можно доказывать R-продолжаемость для некоторого R; в некоторых случаях это оказывается удобным.

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

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

Харкевича в Москве, на семинарах "Теория кодирования", "Дискретный анализ" и "Теория графов" Новосибирского Государственного Университета и Института Математики.

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

Глава Периодичность совершенных раскрасок радиуса 1 бесконечной прямоугольной решетки Граф G(Z2 ) бесконечной прямоугольной решетки является очень популярным объектом при изучении различных комбинаторных конструкций, в частности, упаковок, покрытий и замощений [27, 21]. Довольно часто при этом возникает следующий вопрос: если некоторая конструкция на графе G(Z2 ) существует, то следует ли отсюда существование конструкции с теми же параметрами, обладающей свойством периодичности? Ответ на этот вопрос не всегда оказывается положительным. Например, в работах [27] и [21] рассматривались замощения плоскости плитками. Оказалось, что для некоторого набора плиток замощение существует, но все такие замощения оказываются апериодическими.

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

1.1 Определения и обозначения В этой главе рассматриваются совершенные раскраски радиуса 1, для краткости будем называть их просто совершенными. Периодичность совершенных раскрасок радиуса больше 1 исследуется в третьей главе.

Зафиксируем множество цветов N = {1,..., n} и рассмотрим произвольный граф G. Раскраска вершин графа G в цвета из N с квадратной матрицей A порядка n называется совершенной, если число вершин цвета j, смежных с вершиной цвета i, не зависит от выбора этой вершины и равно aij.

Рассматриваются совершенные раскраски графа G(Z 2 ) бесконечной прямоугольной решетки. Этот граф является регулярным, степень любой его вершины равна 4. Каждой вершине сопоставляется пара целых чисел координат: (x, y), две вершины смежны, если соответствующие им пары отличаются в одной координате на единицу.

Раскраску графа G(Z 2 ) можно понимать как функцию Раскраска называется периодической в направлении (p, q) (p, q целые числа ), если (x + p, y + q) = (x, y) для любых целых чисел x, y.

Совершенная раскраска, периодическая в направлениях (p, p) и (q, q), называется периодической. Направление (p, p) назовем положительным, а направление (q, q) отрицательным; числа p и q назовем периодами соответственно по положительному и отрицательному направлениям.

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

Вершину (x, y) графа G(Z2 ) назовем четной, если x + y четно, и нечетной, если x + y нечетно. Таким образом, множество вершин графа разбивается на две группы.

Раскраске (x, y) сопоставим двудольную раскраску (x, y) следующим образом:

То есть, если одним цветом окрашены четные и нечетные вершины, то вместо этого цвета вводятся два новых цвета, одним из которых окрашены только четные, а другим только нечетные вершины. У двудольной раскраски множество цветов разбивается на две группы, одна из которых соответствует четным, а другая нечетным вершинам. Если раскраска (x, y) совершенная, то также является совершенной, ее матрица M имеет вид:

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

Совершенную раскраску назовем периодической по четным вершинам в направлении (p, q), где p + q четное, если (x + p, y + q) = (x, y) для любой четной вершины (x, y). Совершенную раскраску, периодическую в направлениях (p, p) и (q, q) по четным вершинам, назовем периодической по четным вершинам. Аналогично вводится определение периодичности по нечетным вершинам.

Раскраска может быть периодической и непериодической в положительном и отрицательном направлениях по четным и нечетным вершинам (всего 8 возможностей).

Цвета i и j назовем эквивалентными, если в соответствующей матрице i-я и j-я строки совпадают.

Введем операцию редукции для эквивалентных цветов в двудольной раскраске: объединение цветов i и j в один цвет.

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

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

Аналогично вводится операция редукции для нечетных цветов.

Дальнейшие определения даются с точностью до поворота на /2 и зеркального отражения.

Определим бесконечную диагональ в положительном (отрицательном) направлении как множество вершин с координатами (i + d, j + d) (соответственно (i d, j + d)), где i, j фиксированные целые числа, d произвольное целое число.

n-диагональю в положительном (отрицательном) направлении назовем множество вершин с координатами (i+d, j+d) (соответственно (id, j+d)), где i, j фиксированные целые числа, d {0,..., n 1}. Вершину (i, j) назовем начальной. Для бесконечной диагонали в качестве начальной вершины можно выбрать произвольную вершину из диагонали. Положительную n-диагональ обозначим через Dn (i, j), отрицательную через Dn (i, j) Любой положительной (отрицательной) диагонали поставим в соответствие слово (i, j), (i+1, j +1),.., (i+n1, j +n1) (для отрицательной слово (i, j), (i 1, j + 1),...(i n + 1, j + n 1)). Диагонали будем считать одинаковыми, если соответствующие им слова совпадают.

Бинарная диагональ это бесконечная диагональ, состоящая из двух чередующихся цветов. Бинарная n-диагональ это n-диагональ, состоящая из двух чередующихся цветов. Бинарную n-диагональ будем обозначать Bn,x,y (i, j) или Bn,x,y (i, j), где x и y соответствующие цвета, для сокращения записи иногда будем опускать индексы x и y.

В дальнейшем иногда для удобства вместо графа G(Z 2 ) будем рассматривать двойственный ему граф, так как эти графы изоморфны и будем говорить не "вершина", а "клетка". В частности, на рисунках для наглядности окрашены клетки.

На рис. 1.1 изображена положительная бинарная диагональ.

В дальнейшем не теряя общности будем как правило начинать рассуждения с диагоналей положительного направления.

Рис. 1.1. Бинарная диаго- Рис. 1.2. Двойное слово и Рис. 1.3. Четное двойное Диагональное двойное слово длины n, (n целое, n 2) определим как две n-диагонали одного направления со смежными начальными вершинами. Бесконечное диагональное двойное слово это две бесконечные диагонали одного направления, у которых начальные вершины можно выбрать так, чтобы они были смежными.

На рис. 1.2 черными кружками изображено такое двойное слово.

Продолжение двойного слова, состоящего из двух n-диагоналей в положительном направлении с начальными вершинами (i, j) и (i 1, j) это nдиагональ с началом (i, j 1). Такое двойное слово будем обозначать через DDn (i, j), а его продолжение через rn (i, j). Можно также рассматривать продолжение в другую сторону, т. е. положительную n-диагональ с началом (i 1, j + 1), обозначим его через ln (i, j). На рис. 1.2 белыми кружками изображено продолжение двойного слова.

Двойные слова DDn (i, j) и DDn (k, l) будем считать одинаковыми, если их n-диагонали Dn (i, j) и Dn (k, l), Dn (i 1, j) и Dn (k, l 1) попарно одинаковы.

Положительное двойное слово, состоящее из двух n-диагоналей в положительном направлении с начальными вершинами (i, j) и (i, j + 1), будем обозначать через DDn (i, j); его продолжения n-диагонали с начальными вершинами (i + 1, j) и (i 1, j + 1) через ln (i, j) и rn (i, j).

Аналогично можем определить двойное диагональное слово в отрицательном направлении и его продолжения; нам потребуется бесконечное двойное диагональное слово DD (i, j), состоящее из двух бесконечных диагоналей D (i, j) и D (i+1, j), и его продолжения l (i, j) и r (i, j), которые являются диагоналями соответственно D (i 1, j) и D (i + 2, j).

Конечное четное диагональное двойное слово длины n (где n целое число) определим как две n-диагонали Dn (i, j) и Dn (i 1, j + 1). Такое слово обозначим через En (i, j). На рис. 1.3 черными кружками изображено четное двойное слово.

Продолжение четного двойного слова это n-диагональ Dn (i+1, j 1).

На рис. 1.3 белыми кружками изображено продолжение четного двойного слова.

Две бинарные n-диагонали (два диагональных двойных слова, четных двойных слова) в положительном направлении назовем парными, если одно получается из другого сдвигом на вектор, коллинеарный вектору (1, 1).

Аналогично определяется парность для слов в отрицательном направлении.

1.2 Теорема о периодичности Основной целью настоящей главы является доказательство следующей теоремы:

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

Под сдвигом бинарной диагонали, состоящей из цветов x и y, понимается следующая операция: каждая вершина цвета x из бинарной диагонали красится в цвет y, а каждая вершина цвета y в цвет x.

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

Предложение 1 Совершенная раскраска является периодизуемой тогда и только тогда когда периодизуемая.

Доказательство. Если является периодизуемой, то существует периодическая совершенная раскраска с той же матрицей. Но тогда также является периодической и с такой же матрицей, как и (с точностью до сдвига ). Покажем это. Если какой-либо цвет в раскрасках и имеет одну четность, то цветовой состав окружения его в раскрасках и такой же, какой и у исходной раскраски, только с оттенком четности. Значит, достаточно показать, что наборы четных и нечетных цветов в раскрасках и совпадают. Предположим, что это не так. Тогда существуют два цвета i и j, такие что в раскраске они принадлежат вершинам одной доли, а в раскраске разным. Тогда в раскраске существует путь нечетной длины, соединяющий эти вершины, окрашенный цветами i, k1.., kl, j. Но тогда и в раскраске можно найти такой путь, то есть вершины принадлежат разным долям. Противоречие. Таким образом, цветовой состав окружения любой вершины из совпадает с цветовыми составом окружения вершины такого же цвета из, и наборы цветов совпадают.

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

Таким образом, вопрос периодизуемости совершенной раскраски сводится к вопросу периодизуемости двудольной совершенной раскраски. Поэтому в дальнейшем мы будем рассматривать только двудольные раскраски.

Предложение 2 Раскраска, перидическая в двух неколлинеарных направлениях, является периодической.

Доказательство. Пусть раскраска является периодической в направлениях (p1, q1 ) и (p2, q2 ), то есть для любой вершины (x, y). Тогда то есть, раскраска является периодической в положительном направлении (q1 ·p2 q2 ·p1, q1 ·p2 q2 ·p1 ). Аналогично раскраска является периодической в отрицательном направлении (q2 · p1 q1 · p2, q2 · p1 + q1 · p2 ).

Предложение 3 Раскраска, полученная из совершенной раскраски операцией редукции для некоторых эквивалентных цветов i и j, является совершенной.

Доказательство. В результате проведенной операции цветовой состав окружения вершин той же четности, что и вершины цвета i и j, не меняется, вершины цветов i и j имеют одинаковый цветовой состав окружения по определению, вершины другой четности любого цвета k имеют смежных вершин нового цвета aki + akj, таким образом, новая раскраска действительно является совершенной.

Предложение 4 Продолжения двух одинаковых двойных слов в одну сторону либо одинаковы, либо являются бинарными диагоналями.

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

Заметим, что предложение выполняется не только для одинаковых двойных слов, но и в случае если в каждом из этих слов одна из диагоналей, из которых они состоят, совпадает, а другая является бинарной, и они отличаются только порядком цветов в бинарной диагонали. Например, двойные слова DDn (i, j) и DDn (k, l), такие что их n-диагонали Dn (i, j) и Dn (k, l) одинаковы, а Dn (i 1, j) = Bn,x,z (i 1, j) и Dn (k, l 1) = Bn,z,x (k, l 1), либо продолжаются одинаково, либо бинарными диагоналями.

Предложение 5 Зафиксируем произвольное целое l 2. Тогда если любые парные одинаковые четные положительные двойные слова длины l продолжаются одинаково, то совершенная раскраска является периодической по четным вершинам в отрицательном направлении.

Доказательство. Разобьем четную группу вершин графа на диагональные полосы ширины l, состоящие из парных l-диагоналей положительного направления (то есть Dl+ (i + k, j k), где (i, j) зависит от полосы, k в каждой полосе пробегает все целые числа). В каждой такой полосе встретятся два одинаковых четных слова длины l на расстоянии n2l, они продолжаются одинаково, таким образом, имеется периодичность в отрицательном направлении в каждой из этих полос, причем период n2l. Значит, вся совершенная раскраска является периодической по четным вершинам в отрицательном направлении, причем период (n2l )!.

Предложение 6 Если в совершенной раскраске имеется бинарная n-диагональ длины не менее 6, состоящая из цветов x и y, то эти цвета эквивалентны.

Доказательство. Достаточно доказать для диагонали длины 6, так как любая более длинная диагональ содержит бинарную поддиагональ длины 6. В этой 6-диагонали количество вершин цвета x равно 3. Пусть для некоторого цвета z в матрице совершенной раскраски axz = 0, очевидно, что тогда ayz = 0. Рассмотрим множество вершин, смежных с вершинами 6-диагонали. Этих вершин 14, причем среди них вершин цвета z будет 3axz +C1, где 0 C1 2 (константа C1 возникает из-за граничных вершин).

Аналогично это количество можно выразить так: 3ayz + C2, где 0 C2 2.

Таким образом, Это равенство можно переписать следующим образом:

причем 2 C2 C1 2. Это возможно только если axz = ayz, C2 = C1.

Предложение 7 Пусть совершенная раскраска является непериодической по четным вершинам в отрицательном направлении. Тогда в четной группе цветов встречаются эквивалентные цвета и сколь угодно длинные парные бинарные диагонали в положительном направлении.

Доказательство. Если в нечетной группе цветов есть эквивалентные цвета, то проведем операцию нечетной редукции. Эта операция не изменяет цвета четных вершин и, следовательно, не влияет на периодичность по четным вершинам, поэтому можно рассматривать совершенную раскраску, полученную нечетной редукцией вместо исходной раскраски.

Из предложения 5 следует, что существуют одинаковые парные сколь угодно длинные четные двойные слова в положительном направлении, которые продолжаются по-разному. Возьмем какое-нибудь n (причем его можно выбрать сколь угодно большим) и найдем такие слова длины (n + 1):

En+1 (i, j) и En+1 (i + k, j + k). Докажем, что продолжения этих двойных слов содержат бинарные диагонали длины n. (На рис. 1.4 такое двойное слово помечено буквой v.) Рис. 1.4. Иллюстрация к Рис. 1.5. Иллюстрация к Рассмотрим нечетные вершины, содержащиеся внутри каждого из одинаковых четных двойных слов, то есть диагонали Dn (i, j +1) и Dn (i+k, j k + 1) (на рис. 1.4 помечены буквой x). Цвета соответствующих нечетных вершин в этих нечетных диагоналях будут совпадать, так как эти цвета являются эквивалентными и в результате нечетной редукции объединяются в один цвет. Таким образом, имеется два одинаковых двойных диагональных слова DDn (i, j + 1) и DDn (i + k, j k + 1) (на рис. 1.4 обведены кружком), у которых продолжения rn (i, j + 1) и rn (i + k, j k + 1) по предложению либо одинаковые, либо являются бинарными диагоналями, конечными или бесконечными (на рис. 1.5 эти продолжения обозначены буквой w). Второй случай невозможен, так как по предложению 6 цвета бинарных диагоналей будут эквивалентными и в результате нечетной редукции объединятся в один цвет. Таким образом, снова имеется два одинаковых двойных диагональных слова DDn (i, j) и DDn (i + k, j k) (на рис. 1.5 обведены кружком), у которых продолжения rn (i, j) и rn (i + k, j k) по предложению либо одинаковые, либо являются бинарными диагоналями, конечными или бесконечными (на рис. 1.5 эти продолжения помечены черным кружком).

Так как по построению эти продолжения являются продолжениями исходных четных двойных слов и потому различны, то они являются бинарными диагоналями длины n, что и требовалось доказать.

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

Предложение 8 Если две раскраски, получаемые из исходной совершенной раскраски четной и нечетной редукциями, являются периодическими, то и исходная совершенная раскраска тоже периодическая.

Доказательство. Из того, что совершенная раскраска, получаемая из исходной совершенной раскраски четной редукцией, является периодической, следует, что исходная совершенная раскраска периодическая по нечетным вершинам, так как четная редукция не изменяет цвета нечетных вершин. Аналогично, периодичность совершенной раскраски, получаемой из исходной совершенной раскраски нечетной редукцией, влечет периодичность исходной совершенной раскраски по четным вершинам. Следовательно, исходная совершенная раскраска является периодической по четным и нечетным вершинам в отдельности. Очевидно, что тогда исходная совершенная раскраска будет периодической (в качестве периода можно взять, например, произведение периодов совершенных раскрасок, получаемых четной и нечетной редукциями).

А теперь приступим к доказательству теоремы 1.

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

Рис. 1.6. Иллюстрация к доказа- Рис. 1.7. Иллюстрация к доказательству теоремы 1: двойные слова тельству теоремы 1: двойные слова DDn (i1, j+1) и DDn (i+k1, jk+1) DDn (i, j) и DDn (i + k, j k) и их и их продолжения бинарными диагона- продолжения.

лями.

Пусть 1 является непериодической в отрицательном направлении. По предложению 7 в четной группе цветов существуют сколь угодно длинные парные бинарные диагонали в положительном направлении, которые продолжают одинаковые двойные слова (это следует из доказательства предложения). Рассмотрим такие двойные слова: DDn (i 1, j + 1) и DDn (i + k 1, j k + 1) (на рис. 1.6 обозначены буквой v) длиной n в четыре раза больше периода 1 по нечетным вершинам в отрицательном направлении и их продолжения бинарными диагоналями Bn,x,z (i, j) и Bn,z,x (i + k, j k) (на рис. 6 эти продолжения обозначены буквами x и z). Рассмотрим новые парные двойные слова DDn (i, j 1) и DDn (i + k, j k 1) (на рис. 1. обведены кружком), их продолжения rn (i, j 1) и rn (i + k, j k 1) будут либо будут одинаковыми, либо бинарными диагоналями (на рис. 1. эти продолжения обозначены буквой w). В силу периодичности по нечетным вершинам последнее невозможно, значит, эти продолжения будут одинаковыми и можно рассматривать следующие двойные слова DDn (i, j) и DDn (i + k, j k) (на рис. 1.7 обведены кружком). Заметим также, что каждое из этих двойных слов состоит из двух одинаковых кусков, один из которых находится под жирной ломаной линией на рисунке, а другой над ней (в силу периодичности по нечетным вершинам и выбора длины исходных двойных слов). Продолжения этих парных слов rn (i, j) и rn (i+k, j k) (на рисунке обозначены буквой s) либо одинаковы, либо являются бинарными диагоналями, причем куски каждого из этих продолжений над жирной ломаной и под ней одинаковы.

Рис. 1.8. Иллюстрация к доказательству теоремы 1: бесконечная полоса.

Дальше рассуждаем аналогично, пока не доходим до второй бинарной диагонали (картинки сливаются). Продолжая процесс в обе стороны, мы получим бесконечную полосу, в которой можем рассмотреть два одинаковых бесконечных двойных диагональных слова в отрицательном направлении DD (i + n 1, j + n 1) и DD (i + n 1, j + n 1) (на рисунке отмечены белыми кружками). У них продолжения r (i + n 1, j + n 1) и r (i + n 1, j + n 1) либо одинаковые, либо являются бесконечными бинарными диагоналями (на рис. 8 отмечены черными кружками), а в таком случае можно сдвинуть одну из диагоналей и продолжения станут одинаковыми. Далее рассматриваем диагональные одинаковые слова, состоящие наполовину из старых слов, наполовину из их продолжений продолжения новых слов r (i + n 2, j + n 1) и r (i + n 2, j + n 1), и если они оказываются разными, то есть бинарными диагоналями, то сдвигаем одну из них. Продолжая процесс, получаем совершенную раскраску, периодическую (по построению) по четным вершинам в положительном направлении, причем период не больше удвоенного периода четной редукции по нечетным вершинам.

Теперь в полученной раскраске в силу периодичности в положительном направлении все достаточно длинные бинарные диагонали (больше периода в положительном направлении) являются кусками бесконечных бинарных диагоналей. Бесконечные бинарные диагонали можно сдвигать, поэтому выстроим их так, чтобы все достаточно длинные одинаковые парные диагональные двойные слова продолжались одинаково. Полученная совершенная раскраска является периодической в отрицательном направлении, значит, она периодическая.

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

Таким образом, получена периодическая совершенная раскраска.

Теорема доказана.

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

Предложение 9 Пусть – периодическая совершенная раскраска G(Z 2 ).

Тогда существуют целые числа m и k, такие что (x + k, y) = (x, y) и (x, y + m) = (x, y) для всех x, y Z.

Доказательство. Пусть раскраска является периодической в направлениях (p, p) и (q, q), то есть для любой вершины (x, y). Тогда то есть в качестве k можно взять 2pq (возможно, в качестве k можно взять меньшее число). Аналогично доказывается, что (x, y + m) = (x, y) для m = 2pq.

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

Для доказательства этого факта достаточно применить предложение 9.

Целые числа k и m это размеры тороидального графа G.

Глава Совершенные раскраски радиуса вершин графа G(Z 2) в три цвета В этой главе рассматриваются совершенные раскраски радиуса 1 в три цвета графа G(Z2 ) бесконечной прямоугольной плоской решетки. Матрица A = (aij ) порядка n называется допустимой, если существует совершенная раскраска графа G(Z2 ) в n цветов с матрицей A. Нетрудно видеть, что целесообразно рассматривать только связные матрицы, так как в противном случае для некоторых двух цветов их одновременное существование в раскраске будет невозможно.

В [4] была решена задача описания всех совершенных раскрасок в два цвета бесконечной прямоугольной плоской решетки. Оказалось, что существует ровно 9 допустимых матриц совершенных раскрасок в два цвета, для двух из них существует бесконечное число раскрасок, для остальных одна или две раскраски. В настоящей главе рассматривается аналогичная задача для трех цветов.

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

Для того чтобы не рассматривать эквивалентные матрицы, каждой матрице совершенной раскраски в три цвета сопоставим характеристический вектор, состоящий из ее элементов. В качестве характеристического вектора можно взять (a11, a22, a33, a12, a21, a31 ). По характеристическому вектору матрица совершенной раскраски полностью восстанавливается (предложение 21).

Матрица с лексикографически минимальным характеристическим вектором в классе эквивалентных матриц называется канонической (или имеющей канонический вид).

2.1 Необходимые условия допустимости матрицы В этом параграфе сформулированы и доказаны некоторые необходимые условия допустимости матриц (некоторые из них сформулированы и доказаны для произвольного числа цветов, некоторые для трех, но они легко обобщаются на произвольное число цветов).

Предложение 10 В допустимой матрице совершенной раскраски в n цветов сумма чисел в любой строке равна 4, т. е. ai1 + ai2 +... + ain = при любом i, 1 i n.

Справедливость предложения следует из того, что общее число вершин, смежных с вершиной i, равно ai1 + ai2 +... + ain и совпадает со степенью любой вершины в графе G(Z2 ), которая равна 4.

Предложение 11 Если в матрице A порядка n выполняется aij = 0 и aji = 0, то A недопустима.

Неравенство aij = 0 означает, что каждая вершина цвета i смежна с вершинами цвета j, но это выполняется тогда и только тогда, когда каждая вершина цвета j смежна с вершинами цвета i, т. е. aji = 0. Отсюда следует справедливость предложения.

Предложение 12 Если в матрице A порядка 3 в какой-либо строке одновременно два недиагональных элемента равны нулю ( aki = 0 и akj = 0, i, j, k попарно различны), то A недопустима.

Действительно, если aki = 0 и akj = 0, то akk = 4aki akj = 4. Следовательно, граф G(Z 2 ) окрашивается в цвет k, а это не является совершенной раскраской в три цвета.

Предложение 13 Если в допустимой матрице совершенной раскраски в 3 цвета в каком-либо столбце два недиагональных элемента равны между собой ( aik = ajk, i, j, k попарно различны), то в результате замены цветов i и j одним цветом получается допустимая матрица Доказательство. Рассмотрим совершенную раскраску, соответствующую матрице A. Вершина цвета k имеет akk смежных вершин цвета k и aki + akj вершин, окрашенных в цвета i или j. Каждая вершина цвета i или j имеет aik = ajk смежных с ней вершин цвета k и aii + aij = aji + ajj вершин, окрашенных в цвета i или j.

Предложение 14 Если в матрице совершенной раскраски в n цветов существуют цвета i и j такие, что то в соответствующей совершенной раскраске не существует двух соседних по диагонали вершин различных цветов i и j.

Такие цвета i и j назовем диагонально несовместимыми.

Неравенство (2.1) означает, что вершины цвета i и j имеют менее двух общих смежных вершин, а соседние диагональные вершины имеют две общие смежные вершины.

Предложение 15 Если в матрице A порядка n цвета i и j диагонально несовместимы и существует цвет k (возможно, k = j или k = i ) такой, что aki = 0 и akj = 0, aki + akj 3, то матрица A недопустима.

Такую упорядоченную тройку цветов (k, i, j) назовем противоречивой.

Заметим, что в такой тройке, во-первых, порядок цветов i и j не имеет значения и, во-вторых, может быть, что k = i или k = j.

Доказательство. Предположим, что совершенная раскраска существует. По предложению 14 в совершенной раскраске не существует двух соседних по диагонали вершин различных цветов i и j. Условие aki = 0, akj = 0 и aki + akj 3 означает, что вершина цвета k имеет по крайней мере три смежных вершины, окрашенных цветами i и j. Следовательно, соседние диагональные вершины цвета i будут окрашены цветом j. Противоречие с предложением 14.

Предложение 16 Матрица является недопустимой.

Недопустимость этой матрицы следует из того, что тройка цветов (2, 1, 2) является противоречивой.

Предложение 17 Если матрица порядка 3 удовлетворяет условиям предложения 13 и в результате замены двух цветов одним цветом получается матрица, то исходная матрица недопустима.

Справедливость предложения следует из предложений 16 и 13.

Введем понятие частоты цвета в совершенной раскраске в n цветов. В главе 1 [43] было доказано, что для любой допустимой матрицы существует периодическая совершенная раскраска этого графа. Следствием этого результата является, в частности, то, что для любой совершенной раскраски бесконечной прямоугольной решетки существует совершенная раскраска с той же матрицей конечного тороидального графа. Пусть матрица A допустима. Рассмотрим совершенную раскраску тороидального графа с такой же матрицей (если периодическая раскраска не единственна, то выберем какую-нибудь раскраску; ниже будет доказано, что частота зависит только от матрицы). Пусть N общее число вершин в этом графе, а Ni число вершин цвета i. Частотой цвета i в совершенной раскраске бесконечной прямоугольной решетки с матрицей A назовем величину Предложение 18 Если aij = 0, aji = 0 и совершенная раскраска сущеaji ствует, то отношение частот цветов i и j равно A (j) = aij.

Доказательство. Рассмотрим подграф тороидального графа, вершинами которого являются вершины цветов i и j, а ребрами те ребра, которые инцидентны вершинам двух различных цветов i и j. Этот граф является двудольным, вершины каждой доли окрашены своим цветом. Подсчитаем число ребер в графе двумя способами. Пусть Ni и Nj число вершин цвета i и j соответственно в нем. Тогда, с одной стороны, число ребер равно Ni aij, с другой стороны Nj aji. Следовательно, Заметим, что если aij = aji = 0, то в силу связности матрицы существует последовательность aik1 = 0, ak1 k2 = 0,.., akl j = 0 и отношение частот можно найти следующим образом:

а саму частоту по формуле Таким образом, частота цвета зависит только от матрицы и не зависит от выбора раскраски.

Из предложения 18 вытекает следующее свойство допустимых матриц:

Предложение 19 Если в допустимой матрице совершенной раскраски в три цвета aij = 0 при i = j, 1 i, j 3, то a12 · a23 · a31 = a21 · a32 · a13.

Предложение 20 Если для цвета i совершенной раскраски в n цветов выполняется неравенство A (i) > 1, то aii 2.

Доказательство. Возьмем тороидальный граф с четными периодами (вместо нечетных периодов можно рассматривать в два раза большие).

Разобьем этот граф на квадраты 2 2. Так как частота больше 1, то должен быть квадрат, в котором число вершин цвета i больше 2. Это возможно только в случае, когда aii 2.

Предложение 21 Матрица совершенной раскраски восстанавливается по своему характеристическому вектору (a11, a22, a33, a12, a21, a31 ).

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

2.2 Теорема о совершенных раскрасках в три цвета Основным результатом главы является следующая Теорема 2 Любая допустимая матрица совершенной раскраски в три цвета эквивалентна одной из следующих 21 матриц:

11.

16.

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

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

Назовем матрицу непротиворечивой, если она удовлетворяет следующим свойствам (необходимые условия допустимости матрицы, соответствующие предложениям 10, 11, 12 и 19):

1) сумма чисел в любой строке равна 4, т. е. ai1 + ai2 + ai3 = 4 при любом 3) ни в какой строке одновременно два недиагональных элемента не равны нулю (если aki = 0, то akj = 0, i = k, j = k, i = j);

Упорядочим лексикографически непротиворечивые канонические матрицы по возрастанию характеристического вектора. Такое упорядочение характеристических матриц назовем лексикографическим.

Выпишем возможные тройки диагональных элементов: 000, 001, 002, 011, 012, 022, 111, 112, 122, 222.

Рассмотрим для примера диагональ 000.

1. В лексикографически минимальной матрице a12 = 0. По свойству имеем a21 = 0. Минимальное значение, которое может принимать элемент a31 в этой матрице, равно 1 ( a31 = 0, так как a13 = 0 по предложению 11). Следовательно, a32 = 4 a31 a33 = 3, a23 = 4 a21 a22 = 4, a13 = 4 a11 a12 = 4.

Таким образом, лексикографически минимальной матрицей будет 2. В следующей по порядку матрице a31 = 2, значит, a32 = 2. Таким образом, матрица имеет вид 0 0 4.

3. В следующей матрице a31 = 3, a32 = 1, но эта матрица не является канонической, так как она эквивалентна матрице 0 0 4, у которой меньше характеристический вектор. Значит, в третьей непротиворечивой матрице a12 = 1, a13 = 3. Минимальное значение, которое может принимать элемент a21 в этой матрице, равно 1. Значит, a23 = 4 a21 = 3.

По предложению 19 элементы a31, a32 могут принимать только значения a31 = a32 = 2. Таким образом, третья матрица имеет вид 1 0 3.

4. В четвертой матрице a12 = 1, a13 = 4 a12 a11 = 3, следующее по порядку значение, которое может принимать a21, равно 2, значит, a23 = 2.

По предложению 19 имеем a31 = 3, a32 = 1. Таким образом, получаем матрицу 5. Следующее значение, которое может принимать a21, равно 3. Тогда a23 = 1 и по предложению 19 этот случай не реализуется.

Если a21 = 4, то получим матрицу, эквивалентную матрице 1.

Значит, в пятой матрице a12 = 2, a13 = 2. Минимальное значение, которое может принимать a21, равно 2. (Если a21 < 2, то матрица не является канонической, так как в ней после транспозиции цветов 1 и 2 уменьшается характеристический вектор.) По предложению 19 получаем, что a31 = a32 = 2, т. е. пятая матрица имеет вид Все остальные матрицы не являются каноническими, так как если a 3, то a13 1, и перестановкой цветов 2 и 3 получим эквивалентную матрицу с меньшим характеристическим вектором. Аналогично, если a21 3, то матрица не является канонической.

Таким образом, получены все непротиворечивые канонические матрицы с диагональю 000.

Аналогичным образом перебираются все остальные диагонали и получается 42 непротиворечивые канонические матрицы без 3 на диагонали.

Перебор остальных диагоналей приведен в приложении 1.

Матрицы L1, L2, L5, L10, L11, L13, L14, L15, L20, L21, L27, L31, L32, L33, L34, L35, L37, L41 и L42 являются допустимыми и соответствуют матрицам 1 19 в формулировке теоремы. На рис. 2.1 приведены фрагменты соответствующих совершенных раскрасок, по которым нетрудно восстановить всю совершенную раскраску. В дальнейшем иногда для удобства вместо графа G(Z2 ) рассматривается двойственный ему граф [4, стр. 138–141], так как эти графы изоморфны, и вместо слова "вершина" употребляется слово "клетка". В частности, для наглядности на рисунках окрашены клетки (цвета обозначены цифрами).

L Рис. 2.1. Совершенные раскраски в три цвета.

Матрицы L5, L11, L14, L15, L27, L32, L33 и L34 допускают одну совершенную раскраску (с точностью до поворотов, сдвигов, зеркального отображения и допустимой замены цветов ). Для матриц L13, L20, L31 и L найдено две совершенных раскраски, для матрицы L42 три, для матрицы L37 четыре. Матрицы L1, L2, L10, L21 и L35 допускают бесконечное число совершенных раскрасок (так как при сдвигах бесконечных диагоналей из двух чередующихся цветов раскраска остается совершенной). Еще две матрицы будут рассмотрены ниже. Остальные матрицы являются недопустимыми.

Из предложения 17 следует недопустимость матриц L3 (1, 2), L4 (1, 3), L (1, 2), L19 (2, 3) и L22 (2, 3). Здесь в скобках после каждой матрицы указаны цвета, объединением которых в один цвет получается недопустимая матрица порядка 2.

Из предложения 15 следует недопустимость матриц L7 (3, 1, 3), L8 (3, 1, 3), L9 (3, 1, 3), L16 (3, 1, 3), L18 (2, 1, 3), L24 (2, 1, 2), L25 (2, 1, 2), L (2, 1, 2), L28 (2, 1, 2) и L30 (2, 1, 2). Здесь в скобках после каждой матрицы указана противоречивая тройка цветов для этой матрицы.

Из предложения 20 следует недопустимость матриц L6, L17 и L18, частота цвета 3 больше 2.

Недопустимость матриц L12, L23, L29, L36, L38, L39 и L40 доказывается Рассмотрим для примера матрицу L40 :

Рассмотрим произвольную вершину, окрашенную цветом 1. Для ее окрестности возможно два варианта, в обоих случаях однозначно восстанавливаются цвета еще трех вершин (см. рис. 2.2.1, а, 2.2.1, б). Случай б) не реализуется, так как вершина цвета 2 имеет ровно две смежных вершины цвета 2.

Поэтому вершина цвета 3 неизбежно будет смежна с вершиной цвета 2. В случае а) однозначно восстанавливаются цвета четырех вершин сверху (см.

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

Рис. 2.2. Доказательство недопустимости матрицы L40.

Доказательство недопустимости остальных матриц аналогично доказательству для матрицы L40 и приведено в приложении 2.

Таким образом, рассмотрены все матрицы, которые не содержат 3 на диагонали, и нашли все такие допустимые матрицы. Найдем теперь все совершенные раскраски, в матрице которых хотя бы один из диагональных элементов равен 3. Тогда в каноническом виде матрицы a33 = 3. Рассмотрим произвольную вершину цвета 3. Без ограничения общности можем считать, что ее окрестность выглядит как на рис. 2.3.1.

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

Рассмотрим правую верхнюю вершину цвета 3. Возникает два случая (см. рис. 2.3.3, а, 2.3.3, б).

Рис. 2.3. Совершенные раскраски с цифрой 3 на диагонали.

В случае а) очевидным образом получаем, что еще несколько вершин должны быть окрашены цветом 3 (см. рис. 2.4.1, 2.4.2). Так как раскраска в три цвета и a32 = 0, то a23 = 0 по предложению 11 и a21 = 0 по предложению 12. Следовательно, возникает два случая (см. рис. 2.4.3, а, 2.4.3, б). В обоих случаях получается, что вершина цвета 3 смежна с вершиной цвета 2, получаем противоречие с тем, что a32 = 0. Таким образом, случай а) не реализуется.

Рис. 2.4. Совершенные раскраски с цифрой 3 на диагонали.

Значит, вершины цвета 3 расположены двойными столбцами (см. рис.

2.5.1). Так как вершина цвета 1 смежна с вершиной цвета 2, то получаем следующий слой (см. рис. 2.5.2). Далее возможны два случая (см. рис.

2.5.3, а и 2.5.3, б). В обоих случаях далее однозначно восстанавливаются совершенные раскраски (см.рис. 2.5.4, а и 2.5.4, б) с соответствующими матрицами:

Эти матрицы соответствуют матрицам 20, 21 в формулировке теоремы.

Рис. 2.5. Совершенные раскраски с цифрой 3 на диагонали.

Таким образом, любая допустимая матрица с цифрой 3 на диагонали эквивалентна одной из двух матриц 20 или 21.

Цифры 4 на диагонали в допустимой матрице не может быть по предложению 12. Следовательно, описаны все допустимые матрицы. Теорема доказана.

Приложение В этом приложении приводится перебор характеристических векторов с целью получить все канонические непротиворечивые матрицы. Матрицы с диагональю 000 рассмотрены в тексте главы, для остальных диагоналей выпишем в лексикографическом порядке все характеристические векторы и укажем, какие из них соответствуют непротиворечивым матрицам, какие недопустимым и в силу каких предложений. Для краткости характеристические векторы записаны без скобок и запятых, символ * означает любое число. В таблице напротив каждого вектора стоит либо номер предложения, из которого следует недопустимость матрицы (например, 2), либо номер соответствующей непротиворечивой матрицы или эквивалентной ей канонической матрицы (например, L1 и L1 соответственно). Для диагоналей 001, 002 и 112 рассматриваем только векторы со свойством a12 a21, так как в противном случае матрица не является канонической. Аналогично для диагоналей 111 и 222 должно выполняться a12 aij, для диагоналей 011, 022 и 122 должно быть a12 a13, т. е. a12 2 для диагоналей 011 и 022, а для диагонали 122 должно быть a12 1.

002:

111:

Приложение В этом приложении приводится доказательство недопустимости матриц L12, L23, L29, L36, L38, L39. Доказательство аналогично доказательству для матрицы L40, которое рассмотрено в тексте статьи; начиная с вершины некоторого цвета восстанавливем цвета в окрестности этой вершины и приходим к противоречию. Приведем лишь рисунки, по которым несложно восстановить доказательства. В случае, когда возможно два варианта окрашивания вершин, соответствующие рисунки помечены буквами а), б).

То место, где получается противоречие, помечено кружком.

Рис. 2.6. Доказательство недопустимости матриц L12, L23, L29, L36, L38, L39.

Глава Периодичность совершенных раскрасок радиуса r > 1 бесконечной прямоугольной решетки В этой главе рассматриваются совершенные раскраски произвольного радиуса графа G(Z2 ) бесконечной прямоугольной решетки. Напомним определение совершенной раскраски произвольного радиуса. Пусть G граф, A = (aij ) квадратная матрица порядка n, r 1. Рассмотрим раскраску вершин графа G в n цветов и произвольную вершину x цвета i.

Если количество вершин цвета j (отличных от x) на расстоянии не более r от вершины x не зависит от выбора вершины x и равно aij, то раскраска называется совершенной радиуса r с матрицей A. Назовем матрицу A допустимой, если существует совершенная раскраска графа G(Z2 ) с матрицей A для соответствующего r. Другими словами, раскраска совершенная, если число вершин каждого цвета в шаре радиуса r зависит только от цвета центра этого шара.

Примеры совершенных раскрасок графа G(Z2 ) в 2 цвета см. на Рис. 3.1.

На рисунках для наглядности окрашены клетки вместо вершин, то есть фактически рассматривается граф, двойственный к G(Z2 ) и изоморфный ему.

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

Заметим, что случай r 2 принципиально отличается от случая r = 1.

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

В [4] М. Аксенович классифицировала все допустимые матрицы совершенных раскрасок радиуса 1 в 2 цвета бесконечной прямоугольной решетки и нашла некоторые необходимые условия для того, чтобы матрица была допустимой радиуса r 2. Также была показана периодичность некоторого класса совершенных раскрасок радиуса больше 1 в два цвета.

3.1 Конструкции и примеры В этом параграфе приводятся две конструкции совершенных раскрасок.

Конструкция A. Одним из методов получения совершенных раскрасок является так называемый орбитный метод. Рассмотрим граф G с группой автоморфизмов H, пусть H подгруппы группы H. Если каждую орбиту множества вершин V под действием H раскрасить в свой цвет, получается совершенная раскраска радиуса r N графа G (см. [49]).

Конструкция B. Другой метод получения совершенных раскрасок основывается на объединении цветов.

Лемма 1 Пусть совершенная раскраска радиуса r в n цветов с матрицей A, раскраска получается из объединением цветов в m групп L1,..., Lm. Раскраска является совершенной радиуса r в m цветов тогда и только тогда, когда матрица A удовлетворяет следующему условию:

для любых i, j {1,..., m}, i = j, для любых p, s Li, Матрицей совершенной раскраски является B = (bij )m, где bij = qLj apq, для p Li.

Рис. 3.1. Орбитные раскраски в два цвета.

Примеры.

1. Орбитные раскраски в два цвета. Существует 9 орбитных раскрасок в два цвета (см. Рис. 3.1). Эти раскраски содержатся в множестве совершенных раскрасок радиуса 1, которые были описаны Аксенович [1].

2. Трансляционные раскраски. Пусть H группа трансляций, порожденная двумя неколлинеарными векторами u = (u1, u2 ) и v = (v1, v2 ). Раскрасив каждую орбиту Z2 под действием группы H в свой цвет, получим трансляционную раскраску. Эта раскраска совершенная любого радиуса в |u1 v2 u2 v1 | цветов. Число цветов равно числу вершин в параллелограмме, натянутом на векторы u и v.

3. Совершенный код и раскраски, получаемые из него объединением цветов. Рассмотрим трансляционную раскраску, порожденную векторами (r+1, r) и (r, r1). Эта раскраска совершенная радиуса r в n = 2r2 +2r+ цветов с соответствующей матрицей По лемме 1 мы можем объединить цвета и получить совершенную раскраску с матрицей При k = 0 эта раскраска является совершенным кодом с минимальным расстоянием 2r + 1.

4. Контрпример. В [4] Аксенович рассматривала совершенные раскраски произвольного радиуса бесконечной плоской прямоугольной решетки в два цвета. В статье было выделено два типа совершенных раскрасок, определяемых цветовым окружением вершины на расстоянии 1. Совершенная раскраска называется раскраской типа A, если некоторая вершина имеет нечетное число смежных с ней вершин каждого цвета или вершины одного цвета по горизонтали и вертикали. Совершенная раскраска называется раскраской типа B в противном случае. Все раскраски типа B описаны, они имеют диагональный вид. Доказано, что для раскрасок типа A выполняется |a11 + 1 a21 | 4. В статье было высказано предположение, что для раскрасок типа A выполняется |a11 + 1 a21 | 2.

Это предположение неверно, что показывает следующий контрпример.

Рис. 3.2. Контрпример к предположению |a11 + 1 a21 | 2.

Эта раскраска является совершенной для любого радиуса r. При r 0, 3( mod 4) соответствующая матрица имеет вид При r 1, 2( mod 4) матрица этой раскраски Во втором случае выполняется равенство |a11 + 1 a21 | = 3.

3.2 Периодичность В этом разделе рассматривается периодичность совершенных раскрасок радиуса r > 1 на графе G(Z2 ). Напомним некоторые необходимые определения и обозначения.

Раскраска называется v-периодической (или v – это вектор периодичности раскраски ) если (x + v) = (x) для всех x Z2. Совершенная раскраска, которая является v- и u-периодической для некоторых неколлинеарных v и u, называется периодической. Фундаментальным параллелограммом называется множество вершин в параллелограмме, порожденном векторами u и v. В случае u = (a, 0), v = (0, b) мы используем слово “прямоугольник” вместо слова “параллелограмм”.

Будем говорить, что двумерное слово является R-продолжаемым, если для любых x, z Z2 равенство |BR (x) = |BR (z) влечет |BR+1 (x) = |BR+1 (z). Обозначение |BR (x) = |BR (z) означает, что (x + y) = (z + y) для любых y, таких что y R.

Предложение 22 Если двумерное слово R-продолжаемое, то оно является R -продолжаемым для всякого R R.

Лемма 2 Пусть двумерное слово над конечным алфавитом. Если является R-продолжаемым для некоторого R 0, то периодическое.

Доказательство. Так как алфавит конечный, то существуют два шара BR (x) and BR (y), таких что |BR (x) = |BR (y). Обозначим v = y x.

Докажем, что v вектор периодичности. По Предложению 22 является R -продолжаемым для всякого R R. Поэтому |BR (x) = |BR (y) для всякого целого R. Это означает, что (x + z) = (y + z) для любого вектора z. Рассмотрим произвольную вершину u. Возьмем в качестве z = u x, тогда (u) = (u + v), что означает v-периодичность.

Пусть w вектор, неколлинеарный с v. Рассмотрим бесконечное множество шаров {BR (kw)|k Z}. Существует два шара BR (k1 w) и BR (k2 w), k1 = k2 из этого множества, такие что |BR (k1 w) = |BR (k2 w). Аналогично получаем, что (k2 k1 )w является вектором периодичности. Поэтому периодическое.

Замечание. В качестве следствия из доказательства леммы 2 можно получить, что векторы периодичности могут быть выбраны следующим образом: u = (a, 0) и v = (0, b), где a, b n2R +2R+1 (n это число элементов алфавита, 2R2 + 2R + 1 число вершин в шаре радиуса R). Поэтому число вершин в фундаментальном прямоугольнике a b не более n2(2R +2R+1).

Теорема 3 Пусть : Z2 {1,..., n} совершенная раскраска радиуса r 2 бесконечной прямоугольной решетки. Тогда периодическая.

Доказательство. По лемме 2 достаточно доказать, что является R-продолжаемой для некоторого R r. Мы докажем, что является Rпродолжаемой для R 2r2 + 5r + 1.

Рассмотрим два произвольных шара BR (x) и BR (z), таких что |BR (x) = |BR (z). Нужно доказать, что |SR+1 (x) = |SR+1 (z). Не теряя общности предполагаем, что x = 0.

Нам потребуются некоторые вспомогательные понятия.

Для всякого y Z определим y = y+z, где z определяется как и выше.

Это означает, что y есть трансляция y на вектор z. Соответственно, для всякого подмножества M множества Z2 определим M = {y | y M }.

произвольное подмножество Z2. Обозначим число вершин цвета k в M за Ik (M ). Вектор цветового спектра множества M есть I(M ) = (I1 (M ),..., In (M )). Заметим, что ej = (0,..., 0, 1, 0,..., 0) является вектором цветового спектра вершины цвета j.

Пусть M, N Z2. Определим следующие операции на векторах I(M ) и I(N ):

Аналогично операции I(M ) + I(N ) определяются покомпонентные операции min(I(M ), I(N )) и I(M ) I(N ). Заметим, что если N M =, то Пусть k целое, 1 k 2r + 1. Для шаров BR (0) и Br (y), где y произвольная вершина сферы SRr+k (0), определим k-внешнее множество Ok (Br (y)) следующим образом: Ok (Br (y)) = Br (y) \ BR (0). Другими словами, k-внешнее множество есть множество вершин, которые принадлежат маленькому шару, но не принадлежат большому шару, k есть число слоев вершин в k-внешнем множестве. Пример на Рис. 3.3 приведен для R = 5, r = 2, границы шаров помечены жирной линией, центры шаров отмечены точками. Множество O1 (B2 (2, 2)) состоит из трех вершин v2, v3, v4.

Предложение 23 Если k r, y SRr+k (0), то Доказательство. Доказательство немедленно следует из определения совершенной раскраски и равенства |BR (0) = |BR (0).

Нам потребуются только 1- и 2-внешние множества, поэтому неравенство k r выполняется. Заметим, что для r = 1 и k = 2 это неравенство не выполняется и нельзя применять предложение 23. Это и есть причина того, что случай r = 1 принципиально отличается от r 2.

Теперь все необходимые понятия введены, так что можно приступить к доказательству теоремы. Нужно доказать, что Каждая из сфер SR (0), SR (0) состоит из пяти множеств вершин: SR+1 (0) = Mi, SR+1 (0) = Mi (см. рис. 3.4, клетки в Mi обозначены цифрой i), где M3 = {(j, R + 1 j)|j = 1, 2,..., R}, M5 = {(0, R 1), (0, R + 1), (R + 1, 0), (R 1, 0)}.

Докажем, что |Mi = |Mi, i = 1,..., 5 для каждого множества в отдельности.

Рис. 3.3. Иллюстрация к доказа- Рис. 3.4. Шар B5 (0, 0) радиуса 5; мнотельству Теоремы 3 для R = 5, r = жества M1 –M6 помечены соответствующими цифрами.

Предложение 24 Выполняется |M1 = |M1.

Доказательство. Обозначим за vj вершину (j, j 1 R), где 1 j R, тогда M1 = {v1,..., vR } (см. рис. 3.3, здесь R = 5, r = 2). Предположим противное. Пусть существует i, такое что (vi ) = (vi ). Обозначим (vi ) = a, (vi ) = b.

Доказательство предложения состоит из двух частей.

В первой части будет доказано, что (vi ) = (vi+k(r+1) ) = a, (vi ) = (vi+k(r+1) ) = b для k Z, 1 i + k(r + 1) R. Этот факт будет использован во второй части доказательства. Докажем это для k = 1 (если i + r + 1 > R, то это может быть доказано для k = 1 аналогично). Рассмотрим шары B(i) = Br (i, i 1 R + r), B (i) и 1-внешние множества O1 (B(i)), O1 (B(i)) этих шаров. По предложению 23 имеем I(O1 (B(i))) = I(O1 (B(i))). Тогда Обозначим Тогда Теперь рассмотрим следующие шары B(i + 1) и B (i + 1). Так как O1 (B(i)) O1 (B(i + 1)) = O1 (B(i))\vi = O1 (B(i + 1))\vi+r+1, то По предложению 23 имеем I(O1 (B(i + 1))) = I(O1 (B(i + 1))). Следовательно, (vi+r+1 ) = a, (vi+r+1 ) = b, поэтому (vi ) = (vi+r+1 ), (vi ) = (vi+r+1 ). Аналогично (vi ) = (vi+k(r+1) ) = a, (vi ) = (vi+k(r+1) ) = b для k Z, 1 i + k(r + 1) R. Первая часть доказательства завершена.

Во второй части доказательства предложения рассматриваются элементы сфер SR+2 (0) и SR+2 (0). Рассмотрим шары и C (k), где k Z, 1 i + 1 + k(r + 1) R r + 2, и 2-внешние множества этих шаров. На Рис. 3.5 изображена часть шара BR (0) радиуса R = 17 и пять шаров C(k) радиуса r = 2, центры этих шаров помечены точками. По предложению Рассмотрим множества и Ak (на рис. 3.5 одно из 2-внешних множеств O2 (C(k)) помечено черными и белыми кругами, соответствующее множество Ak помечено белыми кругами). По сути множество Ak является частью 2-внешнего множества O2 (C(k)). Используя (3.1) и (3.2), получаем, что Учитывая эти равенства и (3.3), получаем Аналогично Рис. 3.5. Иллюстрация к доказательству теоремы 3.

Определим множество (см. рис. 3.5). Это множество может быть представлено как объединение непересекающихся множеств Ak и множества D вершин в M6, которые не принадлежат ни одному из множеств Ak (граничные эффекты):

На рис. 3.5 множество D состоит из трех вершин u1, u2, u3. Число элементов в множестве D не более 2r: |D| 2r. Аналогично для множества где |D | 2r. Используя (3.4), получаем Это означает, что мы имеем следующее условие на число вершин цвета a в множествах k Ai+k(r+1) и k Ai+k(r+1) :

Поэтому если взять k 2r+1 (отсюда R (2r+1)(r+1)+2r = 2r2 +5r+1), то множество M6 содержит больше вершин цвета a (и, аналогично, меньше вершин цвета b), чем множество M6.

Далее, существует j, такое что (vj ) = a и (vj ) = (vj ). Действуя как и ранее, получаем, что множество M6 содержит больше вершин цвета a, чем множество M6. Противоречие. Предложение доказано.

Таким образом, доказано, что |M1 = |M1. Доказательство аналогично для множеств M2, M3, M4. Далее, (0, R 1) = (0, R 1), так как цвета остальных вершин в шарах Br (0, r R 1) и Br (0, r R 1) одинаковые. Аналогично для других элементов множества M5.

Таким образом, мы имеем, что |SR+1 (0) = |SR+1 (x ), отсюда является R-продолжаемой для R 2r2 + 5r + 2. Теперь по лемме 2 функция периодическая. Теорема доказана.

Из доказательства теоремы 3 и замечания к лемме 2 можно получить верхнюю границу на число вершин в фундаментальном прямоугольнике:

Следствие 2 Пусть совершенная раскраска радиуса r 2 в n цветов бесконечной прямоугольной решетки. Тогда число вершин в фундаментальном прямоугольнике для не более чем n2(2(2r +5r+1) +2(2r +5r+1)+1).

Заметим, что если v и u векторы периодичности совершенной раскраски, то может быть получена объединением цветов (Конструкция B) из трансляционной раскраски, порожденной векторами v и u (Конструкция A, пример 2). Следствие 2 дает верхнюю оценку на число цветов в соответствующей трансляционной раскраске: это число не более чем n2(2(2r +5r+1) +2(2r +5r+1)+1).

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

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

В этой главе рассматривается другое обобщение совершенных кодов центрированные функции.

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

Понятие центрированной функции было введено в [31] как обобщение понятия совершенного кода. Если f : Zn {0, 1} 1-центрированная функция радиуса r, то вершины, в которых функция принимает значение 1, образуют совершенный код с расстоянием 2r+1. Далее рассматриваются только 0-центрированные функции и называются просто центрированными.

Пусть G = (V, E) граф. Расстояние между двумя вершинами x и y, обозначаемое d(x, y), это обычная графская метрика. Шар Br (x) радиуса r с центром в вершине x определяется следующим образом:

Аналогично сфера Sr (x) задается следующим условием:

Функция : V Z называется центрированной радиуса r, если для каждого x V.

Функция : V Z называется квазицентрированной радиуса r, если для каждого x V.

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

4.1 Бесконечная прямоугольная решетка В этом параграфе изучается периодичность центрированных и квазицентрированных функций на графе G(Z2 ) бесконечной прямоугольной решетки. Будем рассматривать M -ограниченные функции на Z2, то есть : Z2 Z, такие что |(x)| M для некоторого целого M. Такие функции могут рассматриваться как двумерные слова над конечным алфавитом {M,..., 1, 0, 1,..., M }.

Периодичность функций определяется аналогично периодичности совершенных раскрасок (см. главу 3).

Теорема 4 Пусть : Z2 Z ограниченная центрированная функция радиуса r. Тогда периодическая.

Доказательство. По лемме 2 достаточно доказать, что является R-продолжаемой для некоторого R > r.

Рассмотрим два произвольных шара BR (x) и BR (y), таких что |BR (x) = |BR (y). Достаточно доказать, что |SR+1 (x) = |SR+1 (y). Рассмотрим функцию Мы получаем, что |BR (0) = 0 по определению функции. Для того чтобы доказать, что является R-продолжаемой, достаточно доказать, что |SR+1 (0) = 0. Заметим, что если функция M -ограниченная, то функция 2M -ограниченная.

4.1), где множества Mi определяются как в предыдущей главе.

Сначала докажем, что (x) = 0 для x M1. Обозначим ai = (i, i 1 R), i = 1,..., R. Рис. 4.2 иллюстрирует наши рассуждения для случая R = 5, r = 2.

Рассматривая суммы значений в шарах Br (j, j 1 + r R), получаем j+r ai = 0, j = 1,..., Rr. Отсюда aj+r+1 = aj для всякого 1 j Rr 1, i=j т. е. последовательность ai периодическая с периодом (r + 1).

Теперь рассмотрим элементы сферы SR+2 (0). Обозначим bi = (i, i R), i = 1,..., R + 1 (см. рис. 4.2). Рассматривая суммы значений в шарах bj+r+1 bj = aj1 aj. Так как ai периодическая, то bj+k(r+1) bj+(k1)(r+1) = aj1+(k1)(r+1) aj+(k1)(r+1) = aj1 aj. Суммируя по k, для которых bзначения определены, получаем bj+k(r+1) bj = k(aj1 aj ). Если aj1 = aj для j = 2,..., R, то при достаточно большом R для некоторого i значение bi по модулю будет больше 2M (так как |aj1 aj | 1, то значение R не зависит от aj и aj1 ). Поэтому ai константа. Таким образом, ai = 0 для i = 1,..., R.

Мы доказали, что (x) = 0 для x M1. Доказательство аналогично для 0, аналогично для других элементов M5.

Таким образом, имеем |SR+1 (0) = 0, то есть является R-продолжаемой для некоторого R. По лемме 2 периодическая. Теорема доказана.

Теорема 5 Пусть : Z2 Z ограниченная квазицентрированная функция радиуса r. Если r четно, то функция периодическая.

Доказательство. Доказательство теоремы 5 аналогично доказательству теоремы 4. Если r нечетно, то существует периодические и непериодические квазицентрированные функции радиуса r, примеры в следующем параграфе.

Рассмотрим функцию так же, как в доказательстве теоремы 4. Для того чтобы доказать, что является R-продолжаемой, нужно доказать, что |SR+1 (0) = 0.

Рассматривая суммы значений на сферах Sr (j, j 1+r R), получаем j+r ai = 0. Отсюда aj+r+1 = aj для 1 j R r 1, т. е., последовательi=j ность ai периодическая с периодом (r + 1).

Здесь нам не требуются вершины на сфере SR+2 (0). Рассмотрим значения на сфере SR+3 (0). Обозначим ci = (i+1, i2R), i = 1,..., R (см. рис.

4.2). Рассматривая суммы значений функции в соответствующих сферах, откуда cj+r+1 cj = aj1 aj+1. Так как ai периодическая, то cj+k(r+1) cj+(k1)(r+1) = aj1+k(r+1) aj+1+k(r+1) = aj1 aj+1. Суммируя по k, для которых c-значения определены, получаем, что cj+k(r+1) cj = k(aj1 aj+1 ).

Если aj1 = aj+1 для j = 2,..., R 1, то для достаточно большого R для некоторого i значение ci будет больше 2M по модулю. Ограниченность функции влечет ограниченность, таким образом, a2i = a, a2i+1 = b для каждого i, для которого a-значения определены. Если r четно, то a = то ai = 0 для i = 1,..., R. (Если r нечетно, то возможна ситуация, когда aj ненулевые: a2i = a, a2i+1 = a.) Окончание доказательства такое же, как и для теоремы 4. Теорема доказана.

4.2 Примеры В этом параграфе описываются некоторые конструкции центрированных и квазицентрированных функций радиуса 1 на Zn. Эта конструкция дает примеры, которые показывают, что теорема 4 выполняется только для двумерного случая.

Пусть : Zk Z, : Zm Z. Рассмотрим функцию : Zk+m Z, определенную следующим образом:

Лемма 3 1. Если центрированная функция радиуса 1, квазицентрированная функция радиуса 1, то является центрированной функцией радиуса 1.

2. Если и квазицентрированные функции радиуса 1, то является квазицентрированной функцией радиуса 1.

2. Доказательство аналогично доказательству первой части леммы.

Пример 1. Функция : Z2 Z, заданная следующей формулой:

является непериодической квазицентрированной функцией для любого нечетного r.

Пример 2. Пусть центрированная функция радиуса 1 на Z1 :

Функция (x, y, z) = (x, y)(z) является центрированной радиуса 1 и непериодической; более того, носителем этой функции является плоскость x = y (в зависимости от a и b носитель может быть меньше).

Пример 3. Функция (x, y, z) = (x, y, z) + (y, z, x) + (z, x, y) является центрированной радиуса 1 и не (p, q, s)-периодической для всякого (p, q, s) = (0, 0, 0).

4.3 Бесконечные треугольная и гексагональная решетки В этом параграфе рассматривается периодичность центрированных и квазицентрированных функций на бесконечной треугольной и гексагональной решетках (см. рис. 4.3 и рис. 4.4). Все необходимые определения, вспомогательные предложения и леммы могут быть сформулированы аналогично бесконечной прямоугольной решетке. Но необходимо сделать замечание о гексагональной решетке. Граф гексагональной решетки двудольный, и шары с центрами в вершинах из разных долей не могут быть получены один из другого трансляциями. Поэтому функция на этом графе считается R-продолжаемой, если она R-продолжаемая для каждой доли в отдельности. Множества вершин бесконечной гексагональной и треугольной решеток обозначим через H и T соответственно.

Эти графы двойственны. Для наглядности рисунки иллюстрируют функции на гранях двойственных графов вместо функций на вершинах графов.

Рис. 4.5 и 4.6 иллюстрируют примеры центрированной функции радиуса 1 на вершинах бесконечной треугольной решетки и квазицентрированной функции радиуса 1 на вершинах бесконечной гексагональной решетки.

rrrrrrr rrrrrrrr rrrrrrrr rrrrrrr rrrrrrrr rrrrrrr rrrrrrrr rrrrrrr rrrrrrrr rrrrrrr Теорема 6 Пусть : T Z ограниченная центрированная (квазицентрированная) функция радиуса r на бесконечной треугольной решетке.

Тогда периодическая.

Доказательство теоремы 6 аналогично доказательству теоремы 4.

Теорема 7 Пусть : H Z ограниченная центрированная функция радиуса r 3 на бесконечной гексагональной решетке. Тогда функция периодическая.

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

Теорема 8 Пусть : H Z ограниченная квазицентрированная функция радиуса r на бесконечной гексагональной решетке. Тогда функция периодическая.

Доказательство аналогично доказательству теоремы 7.

Примеры. Примеры непериодических центрированных функций радиусов 1 и 2 на бесконечной гексагональной решетке даны на Рис. 4.7 и Рис.

4.8.

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

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

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

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

Во-вторых, сферы четного и нечетного радиусов должны рассматриваться отдельно, потому что они отличаются структурой границы. Сфера четного радиуса r выглядит как шестиугольник со сторонами длины 2 + 1. Сфера нечетного радиуса r имеет стороны чередующихся длин r+1 (сторона с вершинами типа 2 и две дополнительные вершины типа 3) и r+1 + 1 (сторона с вершинами типа 1 и две дополнительные вершины типа). Эти длины могут быть записаны в общем виде: 2 + 1 (сторона с вершинами типа 2) и r+1 + 1 (сторона с вершинами типа 1). Рис. 4.9 и 4.10 иллюстрируют шары радиусов 5 и 6 соответственно. В-третьих, в доказательстве теоремы нам придется рассматривать до 4-х слоев вершин вместо 2 слоев, чтобы получить противоречие. Это и является причиной того, что теорема выполняется только для r 3.

Идея доказательства заключается в следующем. Как и для бесконечной прямоугольной решетки, достаточно доказать, что существует R Z, такое что для всякой вершины x условие |BR (x) = 0 влечет |SR+1 (x) = 0. Мы получим некоторые условия на значения функции на вершинах слоя i (т.

е. вершины сферы SR+i (x)), рассматривая шары радиуса r с центрами в вершинах сферы SRr+i (x). Рис. 4.11 и 4.12 иллюстрируют часть шара радиуса R с нулевыми значениями (его граница помечена жирной линией) и 4 слоя вершин. Вершины слоев 1-4 обозначены ai, bi, ci, di соответственно.

Используя условия для слоев 1-4, мы докажем, что если ai = 0, то на одном из этих слоев возникают растущие значения, что противоречит ограниченности функции. Теперь рассмотрим детали доказательства в каждом случае.

Случай 1 (r четное, вершины сферы радиуса R + 1 типа 1). См. рис.

4.11.

В этом случае нужно рассмотреть 4 слоя. Обозначим n = 2 + 1.

Значения первого слоя (a1, a2,..., ap, p = R ). Ниже формулы выполняются для всех индексов, для которых a-значения (или b-, c-, d-значения) определены. Рассматривая суммы значений в соответствующих сферах, получаем ai = 0. Отсюда ai+n = ai, т. е. последовательность ai периi=j одическая с периодом n.

Значения второго слоя (b1, b2,..., bp ).