LINEBURG


страница 1
(всего 6)

ОГЛАВЛЕНИЕ

След. стр. >>

Библиотека
<Математическое просвещение>
Выпуск 28




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


ХРОМАТИЧЕСКИЕ
ЧИСЛА




Издательство Московского центра
непрерывного математического образования
Москва • 2003
УДК 519.1
ББК 22.15
Р18


Аннотация
В сороковые годы XX века известными математиками
П. Эрдёшом и Г. Хадвигером была поставлена одна из самых
коротко формулируемых и в то же время одна из самых ярких
и трудных задач комбинаторной геометрии — задача о нахо-
ждении хроматического числа ?( n ) евклидова пространства n ,
т. е. минимального числа цветов, в которые можно так раскра-
сить точки пространства, чтобы точки, отстоящие друг от друга
на расстояние 1, оказались раскрашенными в разные цвета.
Эта задача до сих пор не решена даже для n=2, т. е. для
плоскости, хотя простотой и естественностью своей постановки
она сразу привлекла внимание всех математиков. К настоящему
времени разработано много интересных и остроумных подходов
к её (пока частичному) решению.
Текст брошюры представляет собой запись лекции, прочи-
танной автором 7 декабря 2002 года на Малом мехмате МГУ для
школьников 9—11 классов.
Брошюра рассчитана на широкий круг читателей, интере-
сующихся математикой: школьников старших классов, студен-
тов младших курсов, учителей.


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



ISBN 5-94057-121-2 © Райгородский А. М., 2003.
© МЦНМО, 2003.


Андрей Михайлович Райгородский.
Хроматические числа.
(Серия: <Библиотека ,,Математическое просвещение“>. Вып. 28).
М.: МЦНМО, 2003. — 44 с.: ил.
Редактор Г. А. Колюцкий.
Техн. редактор М. Ю. Панов. Корректор Т. Л. Коробкова.

Лицензия ИД № 01335 от 24/III 2000 года. Подписано к печати 10/X 2003 года.
Формат бумаги 60?88 116 . Офсетная бумага № 1. Офсетная печать.
/
Физ. печ. л. 2,75 + 0,50 (вкл.). Усл. печ. л. 3,18. Уч.-изд. л. 3,45. Тираж 3000 экз.
Заказ 3923.

Издательство Московского центра непрерывного математического образования.
121002, Москва, Г-2, Бол. Власьевский пер., 11. Тел. 241 05 00.

Отпечатано с готовых диапозитивов
в ФГУП <Производственно-издательский комбинат ВИНИТИ>.
140010, г. Люберцы Московской обл., Октябрьский пр-т, 403. Тел. 554 21 86.
ВВЕДЕНИЕ
Задачу, о которой мы хотим рассказать в этой брошюре,
принято относить к разделу математики, называемому <комбина-
торной геометрией>. Само по себе название раздела уже носит,
по-видимому, довольно интригующий характер. В самом деле, взя-
тые в отдельности, слова <комбинаторика> и <геометрия> понятны
многим. Однако их сочетание выглядит, быть может, немного не-
ожиданно, и потому следует сперва пояснить, о чём идёт речь.
Очень трудно дать общее и вместе с тем исчерпывающее опре-
деление того, что представляет из себя та или иная область мате-
матики. За последние десятилетия математика ушла столь далеко
на пути абстракции и разделы её столь сильно переплелись между
собой, что не всегда возможно чётко разграничить их. Поэтому мы
не будем стремиться здесь к какой-либо всеобщности. Мы толь-
ко ограничимся более или менее ёмкой формулировкой, а также
приведём небольшую историческую справку, которая и будет при-
звана в максимальной мере прояснить ситуацию.
Итак, говоря предельно кратко, комбинаторная геометрия —
это часть математики, изучающая различные вопросы, которые,
с одной стороны, имеют совершенно геометрическую постанов-
ку (скажем, касаются взаимного расположения фигур и точек
на плоскости), а с другой стороны, легко поддаются комбинатор-
ной интерпретации. Термин <комбинаторная геометрия> восходит,
вероятнее всего, к работам выдающегося специалиста в области со-
ответствующих задач Гуго Хадвигера*), и с этим именем мы ещё
будем встречаться в дальнейшем. Конечно, термин появился, как
это обыкновенно и бывает, позже задач, и классическими примера-
ми последних являются: знаменитая проблема Борсука о разбиении
множеств на части (1933), проблемы, связанные с так называемой
теоремой Хелли (1913), задача освещения границы выпуклого те-
ла (1957), з а д а ч а о х р о м а т и ч е с к и х ч и с л а х и др. Именно
последнюю из перечисленных задач мы и обсудим в этой брошюре.
У задачи о хроматических числах, к формулировке которой мы
перейдём лишь в следующей главе, авторов было несколько. Во-
первых, ещё в начале сороковых годов XX века её поставили заме-
чательные математики Гуго Хадвигер и Пол Эрдёш**), во-вторых,
независимо от Эрдёша и Хадвигера ей занимались приблизитель-
но в то же время Е. Нелсон и Дж. Р. Исбелл. В сороковые годы
шла Мировая война, и этим обстоятельством обусловлен тот факт,
что поначалу хроматические числа не вызвали слишком бурного
*) Г. Хадвигер (1908—1981) — известный немецкий математик.
**) П. Эрдёш (1913—1996) — выдающийся венгерский математик, автор более чем
полутора тысяч статей, один из создателей современной венгерской математической
школы, а также автор множества известных — и ныне уже ставших класси-
ческими — задач комбинаторики, геометрии, теории чисел и теории множеств.
3
интереса. Потребовалось около 15 лет, чтобы положение измени-
лось кардинально: после работы Хадвигера 1961 года, посвящённой
нерешённым задачам, хроматические числа стали активно изучать-
ся, и за прошедшие с тех пор десятилетия соответствующая наука
сделалась одной из самых популярных математических дисциплин
в мире. Задачей Эрдёша—Хадвигера занимались многие известные
математики, о ней написаны сотни прекрасных статей, имеются
монографии, и всё же проблема столь нетривиальна и глубока, что
и по сей день остаётся немало неисследованных вопросов, которые
связаны с ней и которые, несомненно, поддаются изучению. В этой
брошюре мы постараемся дать введение в проблематику: поставим
задачу, обсудим ряд ярких и важных результатов, сформулируем
некоторые из нерешённых вопросов.

ПОСТАНОВКА И РЕШЕНИЕ ЗАДАЧИ
В ОДНОМЕРНОМ СЛУЧАЕ
Рассмотрим обыкновенную вещественную прямую, т. е. множе-
ство всех вещественных (действительных) чисел, которое принято
или же 1 , подчёркивая в последнем случае, что эта
обозначать
прямая одномерна*). Точки на прямой суть действительные чи-
сла x, y и т. д., а расстояние между этими точками определяется
естественно — как |x?y|. Заметим, что в определении хромати-
ческого числа (в данном случае хроматического числа прямой)
понятие расстояния будет играть одну из основных ролей.
Определение. Хроматическим**) числом прямой называется
величина ?( 1 ), равная минимальному количеству цветов, в кото-
рые можно так раскрасить все точки 1 , чтобы расстояние между
точками одного цвета не могло оказаться равным единице.
Точек на прямой, разумеется, бесконечно много, и, на пер-
вый взгляд, определение может показаться не совсем понятным.
Однако, в действительности, если речь идёт о раскраске какого-ни-
будь множества в несколько цветов, то подразумевается попросту,
что это множество представляется в виде объединения своих не-
пересекающихся частей, которым и присваиваются в дальнейшем
<цвета>. В нашем случае это можно символически записать так:
1 ?V2 ?...?V? ,
1 =V (1)
где для любой пары индексов i, j (1?i??, 1?j??, i=j) выпол-
*) Интуитивное понятие о размерностях 1, 2 и 3 имеется у каждого из нас; однако
в математике используется также и абстрактное (т. е. отвлечённое от повседневной
интуиции) понятие размерности, которое позволяет говорить о <четырёхмерных>,
<пятимерных>, <n-мерных> и даже <бесконечномерных> пространствах. Некоторое
представление об этом понятии мы постараемся дать позже, когда речь пойдёт
о хроматических числах в <большой размерности>.
**) Слово <хроматический> греческого происхождения; в переводе на русский
язык оно означает <цветной>.
4
няется условие Vi ?Vj =? (пересечение Vi и Vj пусто). Тем самым,
величина ?( 1 ) есть, по сути, наименьшее число ?, при котором
существует равенство (1) с дополнительным свойством: какова бы
ни была часть множества вещественных чисел Vi (1?i??) и како-
вы бы ни были точки x, y, принадлежащие этой части, расстояние
между этими точками не должно равняться единице (|x?y|=1).
Коль скоро определение дано, возникает вопрос: а почему, соб-
ственно, мы запрещаем точкам одного цвета находиться именно
на расстоянии 1 друг относительно друга? Чем единица лучше
любого другого вещественного числа и почему бы нам не взять,
скажем, число ? в качестве величины <запрещённого> расстояния?
Ответ практически очевиден: дело в том, что никакой разницы
между числами 1 и ? с точки зрения определения величины ?( 1 )
нет, и единица фигурирует в определении исключительно для кра-
соты. Иными словами, значение ?( 1 ) вовсе не зависит от того,
какое положительное число мы взяли за величину запрещённого
расстояния, так как, имея раскраску 1 =V1 ?V2 ?...?V? , в кото-
рой между точками одного цвета не может быть расстояния a>0,
мы с лёгкостью преобразуем её в раскраску 1 =W1 ?W2 ?...?W? ,
в которой нет одноцветных точек на расстоянии b>0: для этого
мы каждую часть Vi <раздуваем> (или <сжимаем>) в b/a раз, по-
лучая, в конечном счёте, новую часть Wi .


?5 ?4 ?3 ?2 ?1 0 1 2 3 4 5
Рис. 1


Задача Эрдёша—Хадвигера ставится теперь очень просто: нуж-
но отыскать значение величины ?( 1 ). Понятно сразу, что ?( 1 )?
?2, поскольку одного цвета заведомо не хватит: на всей прямой
сколько угодно пар точек, удалённых друг от друга на рассто-
яние 1. Однако это ещё не есть искомое решение, ведь сходу
мы даже не знаем, конечно ли наше хроматическое число. Нуж-
но, стало быть, попытаться придумать какую-нибудь (<хорошую>)
раскраску прямой, которая бы использовала как можно меньшее
количество цветов. Эта раскраска изображена на рис. 1, и имеет
она следующий вид: 1 =V1 ?V2 , где

? ?
+? +?
1 \V
V1 = [2i, 2i+1), V2 = 1= [2i?1, 2i).
i=?? i=??

Ясно, что эта двухцветная раскраска обладает надлежащим свой-
ством, и, следовательно, мы получили теорему:
Теорема I. Имеет место точное равенство ?( 1 )=2.
5
Итак, в случае прямой задача Эрдёша—Хадвигера и ставится,
и решается очень легко. В следующем параграфе мы займёмся этой
задачей для случая плоскости и убедимся в том, что уже тогда
сложность её возрастёт принципиально.
1. Множество V ? 1 называется связным, если любые две его
точки могут быть соединены (<связаны>) отрезком, целиком ле-
жащим внутри V. Существует ли двухцветная раскраска прямой,
при которой каждая из частей, отвечающих цветам, связна?*)
2. Существует ли двухцветная раскраска прямой, при кото-
рой каждая из частей, отвечающих цветам, представляет собой
объединение непересекающихся отрезков (интервалов)? Суще-
ствует ли двухцветная раскраска прямой, при которой одна
из частей есть объединение интервалов, а другая — отрезков?

ДВУМЕРНЫЙ СЛУЧАЙ
В этой главе мы рассмотрим обычную плоскость, которую
принято обозначать 2 . Мы будем представлять себе 2 как мно-
жество всех возможных пар (x1 , x2 ) вещественных чисел x1 , x2 ,
а сами эти пары мы будем называть точками (векторами) и обо-
значать x=(x1 , x2 ). Расстояние между точками на плоскости мы
введём стандартное — евклидово**): если векторы x=(x1 , x2 ) и y=
=(y1 , y2 ) лежат в 2 , то расстояние между ними — это величина
p
|x? y|= (x1 ?y1 )2 +(x2 ?y2 )2 . Определение хроматического числа
плоскости, которое мы теперь готовы дать, дословно повторяет
определение величины ?( 1 ) из предыдущей главы. Достаточно
лишь заменить в старом определении прямую 1 на плоскость 2 .
Как и прежде, хроматическое число мы обозначим греческой
буквой ?, только теперь будем писать ?( 2 ). Естественно, задача
Эрдёша—Хадвигера и здесь состоит в нахождении величины ?.
Лёгкость, с которой мы добились успеха в решении <одномер-
ной> задачи, наводит на мысль, что и в случае плоскости дела
будут обстоять довольно хорошо. Тем более обескураживающе вы-
глядит следующий набор результатов: несмотря на популярность
задачи и на все усилия, которые были в различное время прило-
жены многими замечательными специалистами по комбинаторной
геометрии, известны лишь две весьма прозрачных по своему дока-
зательству классических теоремы сорокалетней давности.

*) Двумя чертами слева выделены тексты упражнений для самостоятельного
решения.
**) Вообще-то, в математике существует расширенное представление о том, что
такое расстояние или, как говорят, <метрика>. В одной из заключительных частей
брошюры мы скажем несколько слов об этом и о том, как трансформируется поня-
тие хроматического числа в зависимости от того, каким определением расстояния
пользоваться.
6
Теорема II. Имеет место неравенство ?( 2 )?4.
Теорема III. Имеет место неравенство ?( 2 )?7.
Иными словами, на плоскости не только не найдено хроматиче-
ское число, но даже <зазор> между имеющимися оценками весьма
велик. Теорема II была доказана в 1961 году братьями Мозера-
ми, а теорема III принадлежит Хадвигеру
A7
A1
(1961 год). Обе они отнюдь не сложны, 1
и мы дадим их полные доказательства.
Д о к а з а т е л ь с т в о т е о р е м ы II.
1 1
В основе доказательства лежит замечатель- 1 1
ная точечная конфигурация, предложен- A5 A3
ная братьями Мозерами и внешне слегка A A6
1 1
2
напоминающая веретено, в связи с чем
1 1
она и носит название <мозеровского ве-
1 1
ретена> (рис. 2). В самом деле, можно
представлять себе, что точки A1 , A2 , A3 ,
A4
A4 образуют <иглу>, составленную из пра-
вильных треугольников с длиной сторо- Рис. 2
ны 1, симметричных относительно общего
основания A2 A3 . То же самое можно сказать и о точках A4 , A5 , A6 ,
A7 : это тоже <игла>, имеющая общую вершину A4 с первой иглой
и повёрнутая так, чтобы между вершинами A1 и A7 обеих игл на-
тягивалась <ниточка> длины 1.
Рассмотрим множество A вершин веретена — точки A1 , A2 , ...
..., A7 . Непосредственным перебором ситуаций может быть доказана
Лемма. Каковы бы ни были три различные точки Ai , Aj ,
Ak ?A , среди них найдётся пара точек (назовём их A и B), та-
ких, что |A?B|=1.
Допустим, что плоскость удалось раскрасить в три цвета. Тогда
и точки множества A отнесены к не более чем трём цветам. Зна-
чит, найдутся три точки Ai , Aj , Ak ?A , имеющие один и тот же
цвет (иначе количество точек во всём A не могло бы равнять-
ся семи), и, следовательно, в силу леммы, две из них окажутся
на расстоянии 1, что противоречит определению хроматического
числа. Таким образом, наше допущение неверно, ?( 2 )?4, и тео-
рема II доказана.
Разобранное доказательство, основываясь на его главной
идее, можно вложить в более широкий контекст. Действительно,
для получения оценки ?( 2 )?4 мы пользовались исключительно
свойствами некоторой конечной точечной конфигурации — мозе-
ровского веретена. Дадим следующее определение.
Определение. Множество точек A на плоскости называется
(M, D)-критической конфигурацией, если мощность множества A
(т. е. число элементов в A ; мощность множества X обычно обозна-
чают через #X ) равна M и в то же время в любом подмножестве F
7
множества A , таком, что #F =D+1, найдётся пара точек F1 , F2
на расстоянии 1.
Определение устроено так, чтобы всякая (M, D)-критическая
конфигурация обладала свойством, аналогичным тому, которое бы-
ло доказано в лемме для мозеровского веретена. Это попросту
означает, что веретено является (M, D)-критической конфигураци-
ей с M=7 и D=2, а понятие критической конфигурации в целом
есть прямое обобщение конструкции братьев Мозеров. Если из лем-
мы мы вывели оценку ?( 2 )?4, то в точности те же рассуждения
при наличии какой-нибудь (M, D)-критической конфигурации по-
зволяют доказать неравенство ?( 2 )?M/D в предположении, что
M делится на D нацело, и неравенство ?( 2 )?[M/D]+1 в про-
тивном случае (здесь через [a] обозначена целая часть числа a,
и, в частности, для веретена [M/D]+1=4).
На первый взгляд, совершенно удивительно, что до сих пор
не удалось <соорудить> какую-либо конструкцию, существенно бо-
лее сложную, чем мозеровская, но критическую и с [M/D]+1>4
(c M/D>4). Тем более это кажется удивительным, что у нас
есть компьютеры, позволяющие производить весьма значитель-
ный перебор. И вместе с тем некоторые нетривиальные соображе-
ния заставляют предположить, что ?( 2 )=4. Во всяком случае,
в 1994 году А. Сойфер доказал, что не существует (M, D)-крити-
ческой конфигурации с [M/D]+1>6 (c M/D>6). Это ещё отнюдь
не означает, что ?( 2 )?6, но и этот факт весьма замечательный.
Д о к а з а т е л ь с т в о т е о р е м ы III. Имея целью обосно-
вать результат Хадвигера, естественно попытаться явно указать
какую-нибудь раскраску плоскости в необходимое число цветов.
Вообще говоря, в математике зачастую встречаются и <некон-
структивные> доказательства (т. е. такие доказательства, которые
позволяют лишь за счёт некоторых соображений убедиться в суще-
ствовании искомого объекта и из которых невозможно выделить
его явного описания), но, памятуя о наглядной простоте кон-
струкции для оценки хроматического
числа 1 , разумно всё же и в двумерной
ситуации попробовать обратиться к на-
7 8 9
7 8 9
7 8 9
7 8 9
глядному методу. Дабы сделать подход
максимально понятным и, более того, го-
товым к дальнейшим приложениям, мы
5 6
4 5 6
4 5 6
4 5 6
4
обсудим сперва неравенство ?( 2 )?9,
доказательство которого является пря-
3
1 2 3
1 2 0,7 мым обобщением доказательства оценки
3
1 2 3
1 2
?( 1 )?2. В самом деле, рассмотрим
квадрат с длиной стороны, равной 2,1,
2,1
и разрежем его на девять более мелких
квадратиков-клеточек со сторонами вели-
Рис. 3
8
7 8 9 7 8 9 7 8 9
7 8 9 7 8 9 7 8 9
7 8 9 7 8 9 7 8 9
7 8 9 7 8 9 7 8 9


5 6 5 6 5 6
4 4 4
5 6 5 6 5 6
4 4 4
4 4 4
5 6 5 6 5 6
5 6 5 6 5 6
4 4 4
1,4
3 3 3
1 2 1 2 1 2

страница 1
(всего 6)

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign