Хроматические числа

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

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

Итак, говоря предельно кратко, комбинаторная геометрия — это часть математики, изучающая различные вопросы, которые, с одной стороны, имеют совершенно геометрическую постановку (скажем, касаются взаимного расположения фигур и точек на плоскости), а с другой стороны, легко поддаются комбинаторной интерпретации. Термин «комбинаторная геометрия» восходит, вероятнее всего, к работам выдающегося специалиста в области соответствующих задач Гуго Хадвигера ¹, и с этим именем мы еще будем встречаться в дальнейшем. Конечно, термин появился, как это обыкновенно и бывает, позже задач, и классическими примерами последних являются: знаменитая проблема Борсука о разбиении множеств на части (1933), проблемы, связанные с так называемой теоремой Хелли (1913), задача освещения границы выпуклого тела (1957), задача о хроматических числах и др. Именно последнюю из перечисленных задач мы и обсудим.

У задачи о хроматических числах авторов было несколько. Во-первых, еще в начале сороковых годов XX в. ее поставили замечательные математики Гуго Хадвигер и Пол Эрдёш ², во-вторых, независимо от Эрдёша и Хадвигера ей занимались приблизительно в то же время Е. Нелсон и Дж.Р. Исбелл.
В сороковые годы шла мировая война, и этим обстоятельством обусловлен тот факт, что поначалу хроматические числа не вызвали слишком бурного интереса. Потребовалось около 15 лет, чтобы положение изменилось кардинально: после работы Хадвигера 1961 года, посвященной нерешенным задачам, хроматические числа стали активно изучаться, и за прошедшие с тех пор десятилетия соответствующая наука сделалась одной из самых популярных математических дисциплин в мире. Задачей Эрдёша–Хадвигера занимались многие известные математики, о ней написаны сотни прекрасных статей, имеются монографии, и все же проблема столь нетривиальна и глубока, что и по сей день остается немало неисследованных вопросов, которые связаны с ней и которые, несомненно, поддаются изучению. Мы постараемся дать введение в проблематику: поставим задачу, обсудим ряд ярких и важных результатов, сформулируем некоторые из нерешенных вопросов.

Постановка и решение задачи в одномерном случае

Рассмотрим обыкновенную вещественную прямую, то есть множество всех вещественных (действительных) чисел, которое принято обозначать R или же R¹, подчеркивая с последнем случае, что эта прямая одномерна ³. Точки на прямой суть действительные числа x, y и т.д., а расстояние между этими точками определяется естественно — как | x – y |. Заметим, что в определении хроматического числа (в данном случае хроматического числа прямой)

Определение. Хроматическим⁴ числом прямой называется величина χ(R¹) равная минимальному количеству цветов, в которые можно так раскрасить все точки R¹, чтобы расстояние между точками одного цвета не могло оказаться равным единице.

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

R¹ = V₁ V₂ ... V_χ, (1)

где для любой пары индексов i, j (1 ≤ i ≤ χ, 1 ≤ j ≤ χ, i ≠ j) выполняется условие V_i ∩ V_j =
(пересечение V_i и V_j пусто). Тем самым, величина χ(R¹) есть, по сути, наименьшее число χ, при котором существует равенство (1) с дополнительным свойством: какова бы ни была часть множества вещественных чисел V_i (1 ≤ i ≤ χ) и каковы бы ни были точки x, y, принадлежащие этой части, расстояние между этими точками не должно равняться единице (| x – y | ≠ 1).

Коль скоро определение дано, возникает вопрос: а почему, собственно, мы запрещаем точкам одного цвета находиться именно на расстоянии 1 друг относительно друга? Чем единица лучше любого другого вещественного числа и почему бы нам не взять, скажем, число π в качестве величины «запрещенного» расстояния? Ответ практически очевиден: дело в том, что никакой разницы между числами 1 и π с точки зрения определения величины χ(R¹) нет, и единица фигурирует в определении исключительно для красоты. Иными словами, значение χ(R¹) вовсе не зависит от того, какое положительное число мы взяли за величину запрещенного расстояния, так как, имея раскраску R¹ = V₁ V₂ ... V_χ, в которой между точками одного цвета не может быть расстояния a > 0, мы с легкостью преобразуем ее в раскраску R¹ = W₁ W₂ ... W_χ, в которой нет одноцветных точек на расстоянии b > 0: для этого мы каждую часть V_i «раздуваем» (или «сжимаем») в раз, получая, в конечном счете, новую часть W_i.

Задача Эрдёша–Хадвигера ставится теперь очень просто: нужно отыскать значение величины χ(R¹). Понятно сразу, что χ(R¹) ≥ 2 поскольку одного цвета заведомо не хватит: на всей прямой сколько угодно пар точек, удаленных друг от друга на расстояние 1. Однако это еще не есть искомое решение, ведь с ходу мы даже не знаем, конечно ли наше хроматическое число. Нужно, стало быть, попытаться придумать какую-нибудь («хорошую») раскраску прямой, которая бы использовала как можно меньшее количество цветов. Эта раскраска изображена на рисунке 1, и имеет она следующий вид: R¹ = V₁ V₂, где

Рис. 1

Ясно, что эта двухцветная раскраска обладает надлежащим свойством, и, следовательно, мы получили теорему:

Теорема 1. Имеет место точное равенство χ(R¹) = 2

Итак, в случае прямой задача Эрдёша–Хадвигера и ставится, и решается очень легко. Далее мы займемся этой задачей для случая плоскости и убедимся в том, что уже тогда сложность ее возрастет принципиально.

1. Множество V R¹ называется связным, если любые две его точки могут быть соединены («связаны») отрезком, целиком лежащим внутри V. Существует ли двухцветная раскраска прямой, при которой каждая из частей, отвечающих цветам, связна?

2. Существует ли двухцветная раскраска прямой, при которой каждая из частей, отвечающих цветам, представляет собой объединение непересекающихся отрезков (интервалов)? Существует ли двухцветная раскраска прямой, при которой одна из частей есть объединение интервалов, а другая — отрезков?

Рассмотрим обычную плоскость, которую принято обозначать R². Мы будем представлять себе R² как множество всех возможных пар (x₁; x₂) вещественных чисел x₁, x₂, а сами эти пары мы будем называть точками (векторами) и обозначать Расстояние между точками на плоскости мы введем стандартное — евклидово ⁵: если векторы

лежат в R², то расстояние между ними — это величина

Определение хроматического числа плоскости, которое мы теперь готовы дать, дословно повторяет определение величины χ(R¹) из предыдущей главы. Достаточно лишь заменить в старом определении прямую R¹ на плоскость R². Как и прежде, хроматическое число мы обозначим греческой буквой c, только теперь будем писать χ(R²). Естественно, задача Эрдёша–Хадвигера и здесь состоит в нахождении величины χ.

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

Теорема 2. Имеет место неравенство χ(R²) ≥ 4.

Теорема 3. Имеет место неравенство χ(R²) ≤ 7.

Иными словами, на плоскости не только не найдено хроматическое число, но даже «зазор» между имеющимися оценками весьма велик. Теорема 2 была доказана в 1961 г. братьями Мозерами, а теорема 3 принадлежит Хадвигеру (1961). Обе они отнюдь не сложны, и мы дадим их полное доказательство.

Доказательство теоремы 2. В основе доказательства лежит замечательная точечная конфигурация, предложенная братьями Мозерами и внешне слегка напоминающая веретено, в связи с чем она и носит название «мозеровского веретена» (рис. 2). В самом деле, можно представить себе, что точки A₁, A₂, A₃, A₄ образуют «иглу», составленную из правильных треугольников с длиной стороны 1, симметричных относительно общего основания A₂A₃. То же самое можно сказать о точках A₄, A₅, A₆, A₇: это тоже «игла», имеющая общую вершину A₄ с первой иглой и повернутая так, чтобы между вершинами A₁ и A₇ обеих игл натягивалась «ниточка» длины 1.

Рассмотрим множество A вершин веретена — точки A₁, A₂, ..., A₇. Непосредственным перебором ситуаций может быть доказана лемма.

Рис. 2

Лемма. Каковы бы ни были три различные точки A_i, A_j, A_k A, среди них найдется пара точек (назовем их A и B) таких, что

| A – B | = 1.

Допустим, что плоскость удалось раскрасить в три цвета. Тогда и точки множества A отнесены к не более чем трем цветам. Значит, найдутся три точки A_i, A_j, A_k A, имеющие один и тот же цвет (иначе количество точек во всем A не могло бы равняться семи), и следовательно, в силу леммы, две из них окажутся на расстоянии 1, что противоречит определению хроматического числа. Таким образом, наше допущение неверно, χ(R²) ≥ 4 и теорема 2 доказана.

Разобранное доказательство, основываясь на его главной идее, можно вложить в более широкий контекст. Действительно, для получения оценки χ(R¹) ≥ 4 мы пользовались исключительно свойствами некоторой конечной точечной конфигурации — мозеровского веретена. Дадим следующее определение.

Определение. Множество точек A на плоскости называется (M; D)-критической конфигурацией, если мощность множества A (то есть число элементов в A; мощность множества X обычно обозначают через #X) равна M и в то же время в любом подмножестве F множества A таком, что #F = D + 1, найдется пара точек F₁, F₂ на расстоянии 1.

Определение устроено так, чтобы всякая (M; D)-критическая конфигурация обладала свойством, аналогичным тому, которое было доказано в лемме для мозеровского веретена. Это попросту означает, что веретено является (M; D)-критической конфигурацией с M=7 и D=2, а понятие критической конфигурации в целом есть прямое обобщение конструкции братьев Мозеров. Если из леммы мы вывели оценку χ(R²) ≥ 4 то в точности те же рассуждения при наличии какой-нибудь (M; D)-критической конфигурации позволяют доказать неравенство в предположении, что M делится на D нацело, и неравенство в противном случае (здесь через [a] обозначена целая часть числа a, и, в частности, для веретена ).

На первый взгляд, совершенно удивительно, что до сих пор не удалось «соорудить» какую-либо конструкцию, существенно более сложную, чем мозеровская, но критическую и Тем более это кажется удивительным, что у нас есть компьютеры, позволяющие производить весьма значительный перебор. И вместе с тем некоторые нетривиальные соображения заставляют предположить, что χ(R²) = 4 Во всяком случае, в 1994 г. А. Сойфер доказал, что не существует (M; D)-критической конфигурации Это еще отнюдь не означает, что χ(R²) ≤ 6 но и этот факт весьма замечательный.

Доказательство теоремы 3. Имея целью обосновать результат Хадвигера, естественно попытаться явно указать какую-нибудь раскраску плоскости в необходимое число цветов. Вообще говоря, в математике зачастую встречаются и «неконструктивные» доказательства (то есть доказательства, которые позволяют лишь за счет некоторых соображений убедиться в существовании искомого объекта и из которых невозможно выделить его явного описания), но, памятуя о наглядной простоте конструкции для оценки хроматического числа R¹, разумно все же и в двумерной ситуации попробовать обратиться к наглядному методу. Дабы сделать подход максимально понятным и, более того, готовым к дальнейшим приложениям, мы обсудим сперва неравенство χ(R²) ≤ 9 доказательство которого является прямым обобщением доказательства оценки χ(R¹) ≤ 2 В самом деле, рассмотрим квадрат с длиной стороны, равной 2,1, и разрежем его на девять более мелких квадратиков-клеточек со сторонами величины 0,7 (рис. 3).

Рис. 3

Каждый мелкий квадратик окрасим в свой цвет. Чтобы не было неоднозначности, границы квадратиков раскрасим произвольным образом: скажем, общей границе клеточек 1 и 2 присвоим цвет «1» (хотя могли бы с равным успехом присвоить ей и цвет «2») и т.д. Ясно, что каковы бы ни были точки одновременно попадающие в любую фиксированную клеточку, расстояние между ними не превосходит длины диагонали клеточки, то есть величины

Стало быть, в рамках большого квадрата с условиями, которым должна удовлетворять искомая раскраска, все в порядке: точки одного цвета отстоят друг от друга на расстояние, не равное единице. Однако квадрат — это еще отнюдь не всё R². Как поступить? Очень просто: достаточно «замостить» плоскость копиями нашего квадрата, получаемыми посредством параллельных переносов (рис. 4).

Рис. 4

При этом следует, во-первых, применить параллельные переносы и к разбиениям квадратов на клеточки, то есть сохранить как само разбиение, так и нумерацию его элементов (раскраску), а во-вторых, в неоднозначных случаях, возникающих на границах квадратов, выбрать цвета произвольным образом. С тем, что внутри каждого из квадратов, замощающих плоскость, раскраска обладает требуемыми свойствами, мы уже согласились. Однако это не мешает, в принципе, возникновению одноцветных точек , которые бы находились в разных квадратах и были бы при этом таковы, что По счастью, последнее обстоятельство не имеет места: если точки из разных квадратиков окрашены в один цвет, то они заведомо удалены друг от друга на расстояние, не меньшее, чем 20,7 = 1,4 > 1 (см. рис. 4). Тем самым, и впрямь χ(R²) ≤ 9 раскраска абсолютно «эффективна», и тот факт, что она вполне аналогична одномерной, не вызывает сомнений: двумерное чередование квадратов естественно обобщает одномерное чередование отрезков.

Итак, раскраска плоскости в девять цветов получена, и она, безусловно, является обобщением двухцветной раскраски прямой. Однако плоскость, в отличие от прямой, двумерна, свободы действий у нас здесь гораздо больше, и, в частности, ничто не заставляет нас непременно относить к одному цвету те и только те точки, объединение которых есть объединение каких-либо квадратиков (см. упражнение 3). Хадвигеровское рассуждение как раз и базируется на этой дополнительной свободе: оказывается, что вместо квадратов удобнее рассмотреть правильные шестиугольники. Структура раскраски Хадвигера приведена на рисунке 5: это своего рода бесконечные пчелиные соты, распространенные на все R² (чего в природе, разумеется, не бывает). Каждый из замощающих плоскость правильных шестиугольников изначально устроен так, чтобы максимальное расстояние между точками, лежащими в нем, было немного меньше единицы. Смысл слова «немного» сводится тогда к тому, что и расстояние между точками из разных шестиугольников одного цвета окажется «слегка» больше единицы. Иначе говоря, величина ε > 0 подбирается столь маленькой, чтобы, во-первых, для любых двух точек из одного шестиугольника было выполнено условие а, во-вторых, любые векторы из различных одноцветных ячеек обладали свойством где величина ε' > 0 некоторым образом зависела бы от e. Читателю предоставляется самому попытаться отыскать возможные значения упомянутых величин: ничего, кроме знания простейшей планиметрии, для этого не потребуется. Опять-таки, как и в случае раскраски квадратами, неоднозначность в выборе цветов на границах ячеек устраняется взятием произвольного из по крайней мере двух возможных вариантов.

Рис. 5

Теорему 3 мы доказали, причем по ходу дела построили две весьма симметричные по своей природе раскраски плоскости. Повторяя сказанное в начале лекции, можно еще раз заметить, что, конечно же, для получения хорошего результата о хроматических числах вовсе не обязательно стремиться предъявлять конкретные и тем более столь симметричные конструкции. Однако ситуации, изученные нами, допускают глубокую интерпретацию, позволяющую вложить их в существенно более широкий контекст: с одной стороны, это приведет к новому и более нетривиальному пониманию природы возникающей симметрии, с другой стороны, это дает возможность распространить найденные методы на случай бóльших возможностей (о чем подробнее ниже), и наконец, это подскажет нам весьма содержательные задачи, часть из которых решена, в то время как еще очень многие вопросы подлежат исследованию. Прежде чем об этом рассказать, подчеркнем, что «неконструктивных» подходов к реальному улучшению оценки χ(R²) ≤ 7 до сих пор предложено не было и потому тем важнее детально разобраться с положением дел, связанных с «эффективными» методами.

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

Определение. Решеткой на плоскости называется множество всех точек вида

где векторы неколлинеарны (то есть точки (0; 0), (x₁; x₂) и (y₁; y₂) не лежат на одной прямой), а величины a и b принимают любые целочисленные значения. Говорят, что векторы образуют базис решетки .

Простейшим примером решетки является решетка всех векторов с целыми координатами. Эту решетку принято обозначать через Z², и порождена она естественным базисом из векторов (1; 0) и (0; 1). Заметим, что базис в решетке определен неоднозначно, то есть, скажем, Z² можно породить и другой парой векторов, например (2; 1) и (5; 2).

Определение. Разбиением плоскости на многоугольники называется бесконечное множество T, состоящее из таких (многоугольных) фигур T₁, T₂, ..., что их объединение T₁ T₂ ... совпадает со всем R² и что любые две из них пересекаются, как максимум, по элементам границы (сторонам, вершинам).

Типичными примерами разбиения плоскости являются те, с помощью которых мы задали раскраски R² в девять и семь цветов.

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

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

Теорема. Какова бы ни была решетка на плоскости, множество всех многоугольников Вороного отвечающих точкам образует разбиение R². Такое разбиение называется (решетчатым) разбиением Вороного.

Рассмотрим две решетки: решетку Z² и решетку L, порожденную векторами OA и OB, изображенными на рисунке 6,б и распложенными так, чтобы треугольник OAB был правильным с длиной стороны 1. Оказывается, что многоугольники Вороного для Z² суть квадраты, и соответствующее разбиение Вороного — это разбиение, дающее раскраску в девять цветов (рис. 6,а); многоугольники же Вороного для L суть шестиугольные ячейки, образующие, в конечном счете, разбиение Вороного, которое мы, еще не зная «науки», уподобили пчелиным сотам (см. рис. 6,б). Итак, смысл симметрии прояснен: решетка и ее разбиение Вороного являются абсолютно регулярными, симметричными объектами. Заметим, что последняя решетка L называется гексагональной ⁷ и что она играет огромную роль не только в науке о хроматических числах, но и в науке о «плотнейшей упаковке» кругов единичного диаметра на плоскости.

Рис. 6

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

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

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

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

5.  Сделайте то же, что и в упражнении 4, но для случая разбиения на квадраты. Какова наилучшая верхняя оценка в этом случае, то есть может ли быть усилено уже известное нам неравенство χ(R²) ≤ 9 ?

6. Постройте разбиение Вороного, отвечающее решетке, порожденной векторами

Полный текст опубликован: Райгородский А.М. Хроматические числа. — М.: МЦНМО, 2003.

¹ Г. Хадвигер (1908–1981) — известный немецкий математик.

² П. Эрдёш (1913–1996) — выдающийся венгерский математик, автор более чем полутора тысяч статей, один из создателей современной венгерской математической школы, а также автор множества известных — и ныне уже ставших классическими — задач комбинаторики, геометрии, теории чисел и теории множеств.

³ Интуитивное понятие о размерностях 1, 2 и 3 имеется у каждого из нас; однако в математике используется также и абстрактное (то есть отвлеченное от повседневной интуиции) понятие размерности, которое позволяет говорить о «четырехмерных», «пятимерных», «n-мерных» и даже «бесконечномерных» пространствах.

⁴ Слово «хроматический» — греческого происхождения, в переводе на русский язык оно означает «цветной».

⁵ Вообще-то, в математике существует расширенное представление о том, что такое расстояние или, как говорят, «метрика».

⁶ Название «геометрия чисел» звучит, пожалуй, не менее загадочно, чем наш основной термин «комбинаторная геометрия». Не вдаваясь в подробности, скажем лишь, что эта замечательная наука, в главном своем аспекте устанавливающая связь между задачами теории чисел и геометрией, в определенном смысле была известна еще К.Ф. Гауссу (1777–1855) и Л. Эйлеру (1707–1783), но как отдельная и бурно развивающаяся дисциплина оформилась в конце XIX – начале XX века в трудах Г.Ф. Вороного (1868–1908), А.Н. Коркина (1837–1908), Е.И. Золотарева (1847–1878) и Г. Минковского (1864–1909).

⁷ Гексагон (греч.) — шестиугольник.

Райгородский А.