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

13

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

А.РАЙГОРОДСКИЙ, О.РУБАНОВ, В.КОШЕЛЕВ

Введение и постановка задачи

Современная математика – наука почти необозримая. Для того чтобы даже поверхностно ознакомиться с великим множеством ее разделов, требуются годы, а уж на осознание всех задач, которые возникали в математике в разное время, и нескольких жизней не хватит. Однако в этом бескрайнем море задач имеются и своеобразные «маяки» – задачи, на долгие годы определившие развитие тех областей, в рамках которых они появились. Эти маяки помогают математику правильно выбрать для себя направление движения. Одним из таких маяков служит задача о хроматическом числе – именно о ней мы собираемся поговорить в данной статье. Относится она к одному из самых популярных, а на наш взгляд, к одному из самых красивых разделов математики – к разделу, который принято сейчас называть комбинаторной геометрией. По существу, комбинаторная геометрия – это наука о комбинаторных свойствах геометрических объектов. В самостоятельную дисциплину она оформилась лишь в XX веке, и хроматические числа, надо заметить, немало тому поспособствовали. Вот эта задача: каково наименьшее количество цветов, необходимых для такой покраски плоскости (будем называть ее правильной), при которой расстояние между одноцветными точками не может быть равным 1? Упомянутое наименьшее число цветов мы и назовем хроматическим $числом.^{1}$ На первый взгляд, поставленный только что вопрос совершенно элементарен, но мы убедимся постепенно, что вопрос этот весьма глубок и нетривиален. Прежде всего, хочется понять, что же такое «раскраска плоскости». Наверняка неискушенному читателю сходу представляется нечто вроде того, что изображено на рисунке 1. Однако существуют и куда более

Рис. 1

хитрые ситуации. Пусть, например, точка х на плоскости имеет координаты $x_{1}, x_{2}$ (мы будем писать в дальнейшем $x = ( x_{1}, x_{2} ) ).$ Скажем, что точка «синяя», если числа $x_{1}, x_{2}$ рациональные; в противном случае

1 Слово «хроматический» имеет греческое происхождение. Фактически оно переводится как «цветной» или «цветовой».

назовем точку «красной». Возникает двухцветная покраска плоскости, которую так запросто и не нарисуешь. Еще, по-видимому, стоит напомнить, что расстояние |x – y| между точками $x = ( x_{1}, x_{2} )$ и $y = ( y_{1}, y_{2} )$ на плоскости принято находить по формуле x - y =

$( x_{1} - y_{1} )^{2} + ( x_{2} - y_{2} )^{2}$.

Давайте договоримся об обозначениях. В математике плоскость принято обозначать символом $R^{2}$. В то же время слово «хром» в греческом языке начинается с буквы $\chi$ («хи»). Поэтому для хроматического числа

( ) принято обозначение $\chi R^{2}$. И наконец, вкратце об истории задачи. Она была поставлена в 1950 году Э.Нелсоном, которому тогда было 17 лет. Это весьма любопытно и должно воодушевлять молодого читателя: если семнадцатилетнему Нелсону оказалось по силам поставить столь важный для развития науки вопрос, то отчего бы и мне, читателю, не дерзнуть? Очень похожие задачи рассматривал еще известный геометр Г.Хадвигер в 40-е годы XX века; однако, во-первых, Нелсон об этом не знал, а главное, именно он дал современную постановку проблемы – в терминах раскрасок. Огромную популярность принесли задаче Нелсона публикации М.Гарднера, П.Эрдеша и того же Г.Хадвигера. Весьма интересное историческое эссе на эту тему можно найти в заметке А.Сойфера ([1]); имеется также брошюра А.М.Райгородского [2] и его же статья [3]. Мы же перейдем к изучению хроматического числа.

Небольшое отступление

Как мы знаем теперь, задача Нелсона состоит в правильной покраске плоскости с помощью наименьшего количества красок в «палитре». Мы еще успеем убедиться в том, насколько эта задача непроста. А потому разумно сперва попробовать свои силы в решении аналогичной задачи для случая обычной прямой. Что такое правильная покраска прямой? Да то же самое, в общем-то, что и прежде: следует лишь требовать, чтобы одноцветные точки (числа) х, у не отстояли друг от друга на расстояние 1, т.е. чтобы величина |x – y| не равнялась единице. Очевидно, если покрасить прямую в один цвет, то найдется масса таких «иксов» и «игреков», для которых упомянутое выше условие нарушено. Значит, для правильной покраски прямой нужны по крайней мере два цвета. На рисунке 2 такая покраска указана явно.

20

КВАНТ 2008/№3

вим $v_{3}$ (рис.21, в), по $v_{3}$ и $u_{5}$ воспроизведем $v_{2}$ (рис.21,г), а по $v_{2}$ и w воссоздадим $v_{1}$ (рис.21,д). Длина отрезка $v_{1} v_{5}$ равна 0,98… Это почти единица, и все-таки ребра $v_{1} v_{5}$ ни в каком дистанционном графе на имеющемся множестве вершин нет. Тем не менее, верно следующее. Можно так «пошевелить» точку $v_{5}$, сохраняя расстояние между ней и точкой у равным единице, чтобы в результате построений, аналогичных проделанным выше (см. рис.21), возник граф расстояний $G_{2}$ на рисунке 22, у которого с ребром $v_{1} v_{5}$ все

Рис. 22

в порядке. Расчеты показывают, что «правильные» координаты точки $v_{5}$ суть (0,3…, 0,285…). Обоснование постулированного нами факта, а также все сопутствующие вычисления мы оставляем за рамками данной статьи. Они носят скорее технический характер (ведь координаты всех точек находятся при необходимости с любой наперед заданной точностью), и для осознания смысла конструкции вполне достаточно наглядности последнего рисунка. Видно, в частности, что граф $G_{2}$ имеет четырнадцать вершин, двадцать три ребра и не содержит треугольников. Повернем всю конструкцию $G_{2}$ на 90 градусов вокруг центра квадрата. Получится граф $G¢_{2}$. Объе-

Что же дальше?

На самом деле, с результата О’Доннела и Хохберга все только начинается. Во-первых, можно заметить, что, доказывая этот результат, мы обращали внимание лишь на те единичные отрезки, которые нам были нужны для обоснования неравенства $\chi ( G )$ ³ 4. Из них треугольники не складывались, ну и славно. Вообщето, на двадцати трех вершинах вполне могли возникнуть и другие ребра, так что если бы мы попытались рассмотреть их все, то хроматическое число от этого меньше, конечно, не стало бы, а вот треугольники-то, чего доброго, могли появиться. Именно из нежелания возиться с (возможными) лишними ребрами мы сделали соответствующее допущение относительно определения дистанционного графа. В действительности результат предыдущего пункта остается справедливым и без этого допущения. Просто доказательство становится технически чуть более трудным. Заинтересованный

Рис. 23

диняя графы $G_{2}$ и $G¢_{2}$ (без добавления новых ребер), образуем, наконец, граф $G_{3}$ с двадцатью тремя вершинами и сорока двумя ребрами. (Здесь 23 = 14 + + 14 – 5, поскольку вершины квадрата и его центр при повороте остаются на месте; аналогично, 42 = = 23 + 23 – 4, где 4 – число ребер квадрата.) Скучная проверка показывает, что $G_{3}$ выглядит именно так, как он изображен на рисунке 23. Треугольников в нем тоже нет. Не правда ли, куда навороченнее веретена? Что ж, такова плата за отсутствие треугольников. Покажем теперь, что $\chi ( G_{3} )$ ³ 4. В самом деле, пусть вершины графа $G_{3}$ покрашены в три цвета правильно (вершины, соединенные ребром, разноцветны). Назовем цвета красным, желтым и зеленым. Ясно тогда, что либо точки у, w одного цвета, либо таковы точки х, z. Рассмотрим первый случай. Мы имеем право считать, что у и w, например, красные. Предположим, $u_{5}$, напротив, не является красной – скажем, она желтая. Тогда непременно $u_{1}$ зеленая (за счет ребер $wu_{1}, u_{5} u_{1} ), u_{2}$ желтая (ребра $u_{1} u_{2}$ и $yu_{2} ), u_{3}$ зеленая (ребра $u_{2} u_{3}$ и $wu_{3} )$ и $u_{4}$ желтая (см. рис.20,е). Значит, по тем же причинам $u_{5}$ зеленая, и возникает противоречие. Итак, вершины у, $u_{5}, w$ красные. Посмотрим на пятиугольник $v_{1} v_{2} v_{3} v_{4} v_{5}$. Вершина $v_{1}$ соединена ребром с w, и, стало быть, она не красная. Между вершинами $v_{2}$ и $u_{5}$ также проходит ребро, и это не позволяет $v_{2}$ иметь красный цвет. Аналогичные рассуждения показывают, что и три оставшиеся вершины пятиугольника обязаны быть желтыми или зелеными. Следовательно, пятиугольник покрашен в два цвета. Но это, очевидно, невозможно, и мы имеем противоречие с правильностью исходной покраски. Совершенно так же разбирается случай, когда одноцветны точки х и z (именно для этого мы делали поворот). Таким образом, $\chi ( G_{3} )$ ³ 4, и дело в шляпе: граф $G_{3}$ – искомый. Заметим, что не составляет труда раскрасить $G_{3}$ в четыре цвета, так что, конечно, $\chi ( G_{3} ) = 4$.