LINEBURG


<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

3 3 3
1 2 1 2 1 2
3 3 3
1 2 1 2 1 2
3 3 3
1 2 1 2 1 2


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
4 4 4
5 6 5 6 5 6
4 5 6 4 5 6 4 5 6
5 6 5 6 5 6
4 4 4


3 3 3
1 2 1 2 1 2
3 3 3
3 3 3
1 2 1 2 1 2
1 2 3 1 2 3 1 2 3


1,4 1,4
Рис. 4


чины 0,7 (рис. 3). Каждый мелкий квадратик окрасим в свой цвет.
Чтобы не было неоднозначности, границы квадратиков раскра-
сим произвольным образом: скажем, общей границе клеточек <1>
и <2> присвоим цвет <1> (хотя могли бы с равным успехом присво-
ить ей и цвет <2>) и т. д. Ясно, что каковы бы ни были точки x, y,
одновременно попадающие в любую фиксированную клеточку,
расстояние между ними не превосходит длины диагонали клеточ-
p
p
ки, т. е. величины 0,72 +0,72 = 0,98<1. Стало быть, в рамках
большого квадрата с условиями, которым должна удовлетворять
искомая раскраска, всё в порядке: точки одного цвета отстоят друг
от друга на расстояние, не равное единице. Однако квадрат — это
ещё отнюдь не всё 2 . Как поступить? Очень просто: достаточно
<замостить> плоскость копиями нашего квадрата, получаемыми
посредством параллельных переносов (рис. 4). При этом следу-
ет, во-первых, применить параллельные переносы и к разбиениям
квадратов на клеточки, т. е. сохранить как само разбиение, так
и нумерацию его элементов (раскраску), а во-вторых, в неоднознач-
ных случаях, возникающих на границах квадратов, выбрать цвета
произвольным образом. С тем, что внутри каждого из квадратов,
замощающих плоскость, раскраска обладает требуемыми свой-
ствами, мы уже согласились. Однако это не мешает, в принципе,
возникновению одноцветных точек x и y, которые бы находились
в разных квадратах и были бы при этом таковы, что |x? y|=1.
9
5 6 7 3
4 1 2 4
5 6 7 3
4 1 2 4
5 6 7 3
4 1 2 4
5 6 7 3
4 1 2 4

3 5 6 7
1
1 2
2 4
4 1
1 2
2
3 5 6 7
3 5 6 7
1
1 2
2 4
4 1
1 2
2
3 5 6 7

6 7 3 5 6
1 2 4
6 7 3 5 6
1 2 4
6 7 3 5 6
1 2 4
6 7 3 5 6
1 2 4

3 5 6 7 3
4 1 2 4
3 5 6 7 3
4 1 2 4
3 5 6 7 3
4 1 2 4
3 5 6 7 3
4 1 2 4

3 5 6 7
1
1 2
2 4
4 1
1
3 5 6 7
3 5 6 7
1
1 2
2 4
4 1
1
3 5 6 7


Рис. 5


По счастью, последнее обстоятельство не имеет места: если точки
из разных квадратов окрашены в один цвет, то они заведомо уда-
лены друг от друга на расстояние, не меньшее, чем 2·0,7=1,4>1
(см. рис. 4). Тем самым, и впрямь ?( 2 )?9, раскраска абсолютно
<эффективна>, и тот факт, что она вполне аналогична одномер-
ной, не вызывает сомнений: двумерное чередование квадратов
естественно обобщает одномерное чередование отрезков.
Итак, раскраска плоскости в девять цветов получена, и она,
безусловно, является обобщением двухцветной раскраски прямой.
Однако плоскость, в отличие от прямой, двумерна, свободы дей-
ствий у нас здесь гораздо больше, и, в частности, ничто не за-
ставляет нас непременно относить к одному цвету те и только те
точки, объединение которых есть объединение каких-либо квадра-
тиков (см. упражнение 3). Хадвигеровское рассуждение как раз
и базируется на этой дополнительной свободе: оказывается, что
вместо квадратов удобнее рассмотреть правильные шестиугольни-
ки. Структура раскраски Хадвигера приведена на рис. 5: это своего
рода бесконечные пчелиные соты, распространённые на всё 2 (че-
го в природе, разумеется, не бывает). Каждый из замощающих
плоскость правильных шестиугольников изначально устроен так,
чтобы максимальное расстояние между точками, лежащими в нём,
было <немного> меньше единицы. Смысл слова <немного> сводится
тогда к тому, что и расстояние между точками из разных ше-
стиугольников одного цвета окажется <слегка> больше единицы.
Иначе говоря, величина ?>0 подбирается столь маленькой, чтобы,
во-первых, для любых двух точек x, y из одного шестиугольника
было выполнено условие |x? y|?1??, а во-вторых, любые век-
торы x , y из различных одноцветных ячеек обладали свойством
|x? y|?1+? , где величина ? >0 некоторым образом зависела бы
от ?. Читателю предоставляется самому попытаться отыскать воз-
10
можные значения упомянутых величин: ничего, кроме знания
простейшей планиметрии, для этого не потребуется. Опять-таки,
как и в случае раскраски квадратами, неоднозначность в выбо-
ре цветов на границах ячеек устраняется взятием произвольного
из по крайней мере двух возможных вариантов.
Теорему III мы доказали, причём по ходу дела построили две
весьма симметричные по своей природе раскраски плоскости. По-
вторяя сказанное в начале параграфа, можно ещё раз заметить,
что, конечно же, для получения хорошего результата о хрома-
тических числах вовсе не обязательно стремиться предъявлять
конкретные и тем более столь симметричные конструкции. Однако
ситуации, изученные нами, допускают глубокую интерпретацию,
позволяющую вложить их в существенно более широкий контекст:
с одной стороны, это приведёт к новому и более нетривиальному
пониманию природы возникающей симметрии, с другой стороны,
это даст возможность распространить найденные методы на слу-
?
чай больших размерностей (о чём подробнее ниже), и, наконец,
это подскажет нам весьма содержательные задачи, часть из кото-
рых решена, в то время как ещё очень многие вопросы подлежат
исследованию. Прежде чем об этом рассказать, подчеркнём, что
<неконструктивных> подходов к реальному улучшению оценки
?( 2 )?7 до сих пор предложено не было (впрочем, см. приложе-
ние 2), и потому тем важнее детально разобраться с положением
дел, связанных с <эффективными> методами.
Начнём с обещанной интерпретации наших раскрасок. Для
этого нам понадобится ввести несколько определений и сформу-
лировать один довольно тонкий факт из науки, которую принято
называть геометрией чисел*).
Определение. Решёткой ? на плоскости называется множе-
ство всех точек вида ax+by=(ax1 +by1 , ax2 +by2 ), где векторы
x=(x1 , x2 ) и y=(y1 , y2 ) неколлинеарны (т. е. точки (0, 0), (x1 , x2 )
и (y1 , y2 ) не лежат на одной прямой), а величины a и b принимают
любые целочисленные значения. Говорят, что векторы x и y обра-
зуют базис решётки ?.
Простейшим примером решётки является решётка всех век-
торов с целыми координатами. Эту решётку принято обозначать
через 2 , и порождена она естественным базисом из векторов (1, 0)
и (0, 1). Заметим, что базис в решётке определён неоднозначно,

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




B
B
B
B


O
O A
A
O
x1 x1
O A
A




а) б)
Рис. 6

т. е., скажем, 2 можно породить и другой парой векторов, напри-
мер, (2, 1) и (5, 2).
Определение. Разбиением плоскости на многоугольники назы-
вается бесконечное множество T , состоящее из таких (многоуголь-
ных) фигур T1 , T2 , ..., что их объединение T1 ?T2 ?... совпадает
со всем 2 и что любые две из них пересекаются, как максимум,
по элементам границы (сторонам, вершинам).
Типичными примерами разбиения плоскости являются те, с по-
мощью которых мы задали раскраски 2 в девять и семь цветов.
Определение. Пусть дана некоторая решётка ?. Многоуголь-
ником Вороного, отвечающим точке x этой решётки, называется
множество Vx , состоящее из всех точек плоскости, для которых
точка x есть одна из ближайших точек в ?:
|y? x|?|y? z| ? z??}.
2:
Vx ={y?
Доказательство того факта, что для всякой решётки ? и вся-
кой точки x?? множество Vx будет и впрямь многоугольником
(корректность определения) предоставляется читателю в качестве
лёгкого упражнения. Имеет место замечательная теорема, которую
мы не будем доказывать в этой брошюре.
Теорема. Какова бы ни была решётка ? на плоскости, мно-
жество всех многоугольников Вороного Vx , отвечающих точкам
2 . Такое разбиение называется
x??, образует разбиение
(решётчатым) разбиением Вороного.
Рассмотрим две решётки: решётку 2 и решётку ?, порождён-
ную векторами OA и OB, изображёнными на рис. 6, б и располо-
женными так, чтобы треугольник OAB был правильным с длиной
стороны 1. Оказывается, что многоугольники Вороного для 2 суть
12
квадраты, и соответствующее разбиение Вороного — это разбиение,
дающее раскраску в девять цветов (рис. 6, а); многоугольники же
Вороного для ? суть шестиугольные ячейки, образующие, в конеч-
ном счёте, разбиение Вороного, которое мы, ещё не зная <науки>,
уподобили пчелиным сотам (рис. 6, б). Итак, смысл симметрии
прояснён: решётка и её разбиение Вороного являются абсолютно
регулярными, симметричными объектами. Заметим, что послед-
няя решётка ? называется гексагональной*) и что она играет
огромную роль не только в науке о хроматических числах, но
и в науке о <плотнейшей упаковке> кругов единичного диаметра
на плоскости.
Таким образом, мы имеем разумный общий подход к постро-
ению раскрасок плоскости: нужно взять произвольную решётку,
рассмотреть её разбиение Вороного и попытаться в соответствии
с некоторым правилом сообщить цвета многоугольникам Вороно-
го этого разбиения. Методы, используемые в геометрии чисел,
позволяют, однако же, доказать, что ничего лучшего, чем гекса-
гональная решётка, в этом отношении придумать нельзя, т. е. что
в любом решётчатом разбиении Вороного придётся задействовать
не менее семи красок.
Потерпев фиаско на пути отыскания совершенно симметрич-
ных раскрасок 2 , мы имеем полное право усложнить себе задачу
и расширить область поиска за счёт рассмотрения таких разбиений
плоскости, при которых каждая часть представляет собой объеди-
нение многоугольников, не обязательно являющихся множествами
Вороного какой-либо решётки. К сожалению, до сих пор такой
поиск к успеху не привёл. Однако сама деятельность, связанная
с ним, порождает глубокие и важные задачи о природе раскрасок,
имеющие значительный самостоятельный интерес. Мы сформули-
руем их в соответствующем разделе.
3. Докажите, что если цвета в раскраске плоскости суть объ-
единения многоугольников, то понадобится по крайней мере
шесть таких цветов.
4. Найдите нижнюю оценку для минимального числа цветов
в раскраске 2 , при которой каждый цвет есть объединение тре-
угольников.
5. Сделайте то же, что и в упражнении 4, но для случая раз-
биения на квадраты. Какова наилучшая верхняя оценка в этом
случае, т. е. может ли быть усилено уже известное нам неравен-
ство ?( 2 )?9?
6. Постройте разбиение Вороного, отвечающее решётке, поро-
# A
1 2!
ждённой векторами (1, 0),  , !.
!
3 3

*) Гексагон (греч.) — шестиугольник.
13
ТРЁХМЕРНЫЙ СЛУЧАЙ
Мы уже рассмотрели задачу о хроматических числах на пря-
мой ( 1 ) и на плоскости ( 2 ). В результате из всех пространств,
интуитивное представление о природе которых у нас имеется
и которые, тем самым, можно определять без дополнительных
пояснений, неизученным осталось лишь трёхмерное — (евклидо-
во) пространство 3 , состоящее из всех возможных троек веще-
ственных чисел, т. е. точек (векторов) x=(x1 , x2 , x3 ) (где x1 , x2 ,
x3 ? — координаты), и снабжённое (евклидовым) расстоянием
q
|x? y|= (x1 ?y1 )2 +(x2 ?y2 )2 +(x3 ?y3 )2 ,
где x=(x1 , x2 , x3 ), y=(y1 , y2 , y3 ). Величина ?( 3 ) — хроматическое
число трёхмерного пространства — определяется точно так же, как
это было сделано для случаев меньшей размерности, и задача Эр-
дёша—Хадвигера состоит, опять-таки, в её отыскании. Учитывая
сравнительное фиаско, которое мы потерпели в случае плоскости,
понятно, что рассчитывать мы можем только на получение более
или менее хороших оценок для числа ?( 3 ) и что зазор между эти-
ми оценками, скорее всего, возрастёт. В самом деле, наилучшими
к настоящему времени являются следующие теоремы.
Теорема IV (Д. Е. Райский, 1970). Имеет место неравенство
?( 3 )?5.
Теорема V (Д. Кулсон, 2000). Имеет место неравенство
?( 3 )?15.
Исследуя хроматическое число плоскости, мы не напрасно
старались вложить возникавшие оценки в тот или иной более ши-
рокий контекст: помимо всего прочего, найденные нами общие
рецепты позволят теперь обосновать теоремы IV и V.
Д о к а з а т е л ь с т в о т е о р е м ы IV.
Воспользуемся концепцией (M, D)-критиче-
A1 ских конфигураций. Конечно, до сих пор мы
имели представление лишь о плоских кон-
фигурациях такого типа. Однако их опре-
1 деление для 3 выглядит полностью анало-
1
1 гично, и если нам удастся придумать кон-
A3 фигурацию с достаточно большим значением
A2
1
[M/D]+1 или M/D (со значением 5), то всё
1 1
будет в порядке.
A4
Искомая конфигурация является прямым
1
1
обобщением конструкции братьев Мозеров.
1
Действительно, рассмотрим правильный те-
траэдр в 3 с длиной ребра 1 и вершина-
A1
ми A1 , A2 , A3 , A4 (рис. 7). Рассмотрим также
тетраэдр A1 A2 A3 A4 , симметричный первому
Рис. 7
14
C1
A1
A1 B1
B1



A3
B2
B3

A2 A4
B4



A1 A1

Рис. 8 Рис. 9


относительно общего основания A2 A3 A4 (см. рис. 7). Получается
аналог того, что на плоскости мы назвали иглой. Фиксируя <ниж-
ний конец> иглы (точку A1 ), мы поворачиваем иглу в пространстве
так, чтобы <верхний конец> новой (второй) иглы (скажем, век-
тор B1 ) оказался на расстоянии 1 от точки A1 (между A1 и B1
натянулась <ниточка> единичной длины) (рис. 8). В принципе, для
получения полноценного трёхмерного веретена нужно бы образо-
вать ещё и третью иглу с нижним концом в A1 , а верхним —
в такой точке C1 , что одновременно |A1 ?C1 |=1 и |B1 ?C1 |=1
(рис. 9). Эта конструкция имеет важные приложения в комбина-
торной геометрии, но для наших целей хватит и веретена из двух
игл — веретена A1 A2 A3 A4 A1 B2 B3 B4 B1 (см. рис. 8). Непосредственно
очевидно, что это веретено есть (M, D)-критическая конфигурация
с M=9 и D=2 (среди любых трёх вершин веретена найдётся пара
на расстоянии 1). Следовательно, ?( 3 )?[M/D]+1=5, и теоре-

<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign