LINEBURG


<< Пред. стр.

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

ОГЛАВЛЕНИЕ

обстоятельство, что мы рассматривали именно конечные конструк-
ции: ничего нового их бесконечные аналоги нам бы не принесли.

ПРИЛОЖЕНИЕ 2
ХРОМАТИЧЕСКИЕ ЧИСЛА МЕТРИЧЕСКИХ ПРОСТРАНСТВ
Определяя расстояние между векторами в 2 , мы сделали
замечание о том, что такое естественное и вполне отвечающее на-
глядному опыту понятие, вообще говоря, не является единственно
возможным с точки зрения математики. Если правильно выделить
наиболее существенные свойства, которыми обладает стандартное
расстояние, то окажется, что эти же свойства можно положить
в основу общего определения, т. е. считать <расстоянием> всякую
функцию ?(x, y) двух векторных аргументов, которая удовлетворя-
ет упомянутым требованиям. В действительности, довольно легко
понять, что функция ?(x, y)=|x? y|, которой мы до сих пор с успе-
хом пользовались (обычное, <евклидово> расстояние), имеет ровно
три отличительных особенности. Во-первых, она всегда неотри-
цательна и равна нулю только в случае, когда её аргументы
совпадают. Во-вторых, она <симметрична>, т. е. |x? y| есть то же,
что и |y? x| (не имеет значения, откуда начинать мерить рас-
стояние). Наконец, она подчиняется <неравенству треугольника>:
|x? y|?|x? z|+|z? y| (длина любой стороны треугольника с верши-
нами в точках x, y, z не превосходит суммы длин двух других его
сторон). Отталкиваясь от перечисленных свойств, т. е. изначально
их постулируя, мы приходим к понятию метрики, обобщающему
понятие расстояния: метрика — это просто любая функция ?(x, y),
которая обладает этими тремя свойствами функции |x? y|. Про ме-
трику можно говорить очень много; однако, с одной стороны, это
не является целью нашей брошюры, а с другой стороны, уже име-
ется прекрасная брошюра [3]. Отсылая заинтересованного читателя
к этой брошюре, а также к другой литературе, посвящённой ме-
трическим пространствам, мы лишь приводим здесь необходимое
нам определение и обсуждаем непосредственно те вопросы, кото-
рые напрямую связаны с задачей о хроматических числах.
40
Итак, метрическим пространством называется любая пара
(X, ?), где X — это произвольное (абстрактное) множество, а ?=
=?(x, y) — метрика на нём (x, y?X). Классическими примерами
метрических пространств являются, скажем, пространства ( n , ?? ),
где при ??[1, ?) величина ?? задаётся равенством

?? (x, y)=(|x1 ?y1 |? +...+|xn ?yn |? )1/? ,

а при ?=? соответствующая величина есть max{|x1 ?y1 |, ...
..., |xn ?yn |}. В частности, ?2 — это евклидово расстояние. Ещё
одним примером может служить пространство C[0, 1], состоящее
из всех непрерывных функций на отрезке [0, 1] и снабжённое ме-
трикой ?(f, g)=max |f(x)?g(x)|.
x
Коль скоро у нас имеется какое-нибудь метрическое про-
странство (X, ?), мы можем рассмотреть его хроматическое число
?((X, ?), a). Здесь a>0 — величина критического <расстояния>,
т. е. ?((X, ?), a) — это, как всегда, минимальное количество цве-
тов, необходимых для такой раскраски всех элементов (<точек>)
множества X, при которой точки x, y, отстоящие друг от друга
на <расстояние> a (?(x, y)=a), обязательно оказываются рас-
крашенными в разные цвета. Подчеркнём, что в такой общей
ситуации значение критического расстояния может играть весь-
ма существенную роль. Более того, хроматическое число отнюдь
не обязано быть конечным. Заметим, наконец, что ?((X, ?), a)=
=?(G), где G=(V, E) — граф с множеством вершин V =X
и множеством рёбер E={(x, y)?X: ?(x, y)=a}.
Задача об изучении хроматических чисел метрических про-
странств была предложена в 1976 году М. Бендой и М. Перлесом.
Некоторая пикантность положения состоит в том, что соответству-
ющая работа упомянутых авторов ни разу не была опубликована.
Тем не менее она весьма известна среди специалистов, и потому её
по праву можно считать едва ли не одной из самых популярных
неопубликованных математических работ.
Рассмотрим лишь два наиболее важных метрических простран-
ства. Первое метрическое пространство, которое мы хотели бы
здесь упомянуть, — это пространство ( n , ?? ). В отличие от клас-
сического случая с метрикой ?2 , тут всё устроено очень просто:
?(( n , ?? ), 1)=2n . В самом деле, неравенство ?(( n , ?? ), 1)?2n вы-
текает из рассмотрения множества всех n-мерных (0, 1)-векторов:
попарные <расстояния> между этими векторами равны 1, а коли-
чество их есть как раз 2n . В то же время раскраска пространства
( n , ?? ) в 2n нужных цветов строится следующим образом: век-
тору x=(x1 , ..., xn ) присваивается цвет с <именем> (?1 , ..., ?n ),
где ?i =0, если наибольшее целое число ai , не превосходящее xi ,
41
чётно, и ?i =1, если ai нечётно. Ясно, что различных <имён> 2n
и что для любых одноцветных x, y заведомо ?? (x, y)=1.
Другое важное метрическое пространство намного более забав-
но и, уж во всяком случае, куда более нетривиально с точки зрения
проблемы Эрдёша—Хадвигера. Это пространство ( n , ?2 ), где n —
множество всех n-мерных векторов с рациональными координата-
ми. Дело в том, что множество таких векторов всюду плотно в n ,
т. е. у любого вещественного вектора есть сколь угодно близкий
к нему рациональный сосед. Естественно было бы ожидать тогда,
n с критическим
что задача отыскания хроматического числа
расстоянием, равным, допустим, 1*), окажется не менее трудной,
чем классическая <вещественная> задача. Однако ожидание оправ-
дывается лишь наполовину, и набор результатов, приведённых
в таблице, полученных в разные годы для <малых> размерностей,
не может не впечатлять.

Результат Автор, год
1
, ?2 ), 1)=2 фольклор
?((
2
, ?2 ), 1)=2 Вудалл, 1973
?((
3
, ?2 ), 1)=2 Бенда и Перлес, 1976
?((
4
, ?2 ), 1)=4 Бенда и Перлес, 1976
?((
5
7??(( , ?2 ), 1) М. Манн, 2001
5
, ?2 ), 1)?8 Чилакамарри, 1990
?((


Что касается неограниченного возрастания величины n, то
тут всё становится на свои места: удаётся доказать лишь, что
?(( n , ?2 ), 1)?c1 ·1,172n (А. М. Райгородский, 2001 год) и что
?(( n , ?2 ), 1)??( n )?c2 ·3,001n (Ларман и Роджерс, 1972 год),
а стало быть, зазор между верхней и нижней оценками даже более
велик, чем то было в классическом случае. Иными словами, <ве-
щественный> результат Лармана—Роджерса не удалось улучшить
в <рациональной> ситуации. И это несмотря на столь значитель-
ные успехи в размерностях n?5.
В этой брошюре мы не станем приводить доказательства пе-
речисленных фактов. Заметим только, что все нижние оценки
хроматического числа пространства ( n , ?2 ) опять-таки получают-
ся за счёт построения (M, D)-критических конфигураций. Верх-
ние же оценки в малых размерностях вытекают из детально-
го изучения арифметических свойств числителей и знаменателей
n
*) Понятно, что для принципиально, берём ли мы в качестве запретного
расстояния рациональное или иррациональное число.
42
# A # A
p !2 p !2
! !
p p
в дробях 1 , 2 таких, что  1 ! +  2 ! =1. К сожалению, с ростом
! !
q1  q2 
q1 q2
размерности арифметические методы перестают работать.
В заключение сформулируем замечательную гипотезу Бенды
и Перлеса.
Гипотеза. Пусть Gn — это граф, хроматическое число которого
1
есть ?( n ), а Gn — аналогичный граф для рационального про-
2
странства. Тогда любой конечный подграф графа G2 может быть
1
реализован (с сохранением числа вершин и расстояний между
ними) как какой-нибудь конечный подграф графа G4 . 2
Смысл гипотезы в том, что если она верна, то автоматически
верно и равенство ?( 2 )=4. В самом деле, ?(G4 )=4, поскольку
2
?( 4 )=4. Следовательно, хроматическое число любого конечного
подграфа в G4 не превосходит четырёх. Далее, если гипотеза верна,
2
то хроматическое число каждого конечного подграфа в G2 также
1
не может быть больше четырёх. Значит, по теореме Эрдёша—
де-Брёйна ?( 2 )?4.
20. Найдите ?(( 2 , ?1 ), 1). v v
21. Рассмотрим пространство ( 2 ( 2), ?2 ), где 2 ( 2) состоит
из всех возможных двумерных векторов с координатами вида
pv v
p1
+ 2 2. Найдите ?(( 2 ( 2), ?2 ), 1).
q1 q2
22. Рассмотрим в 5 только те векторы, у которых знамена-
тели всех координат нечётны. Чему равно хроматическое число
пространства таких векторов, если, как всегда, метрика евклидо-
ва, а критическое расстояние есть 1?
23. Назовём диаметром множества максимальное расстояние
между принадлежащими ему точками. Докажите, что всякий
трёхмерный многогранник диаметра 1 и с вершинами в рацио-
нальных точках разбивается на две части диаметра меньше 1.
24. Приведите пример метрического пространства с бесконеч-
ным хроматическим числом.

ЗАКЛЮЧЕНИЕ
В этой небольшой брошюре мы постарались рассказать о наибо-
лее важных аспектах классической проблемы Эрдёша—Хадвигера.
Даже из нашего (в сущности, весьма краткого и схематичного) из-
ложения видно, насколько красива и нетривиальна поставленная
задача: и результаты, и разнообразные методы их получения дают
богатый материал для исследования, приводят к появлению но-
вых идей и методов — в комбинаторной геометрии, да и не только
в ней (а ещё и в геометрии чисел, теории графов и т. д.). В дей-
ствительности, нам удалось осветить здесь лишь малую долю мно-
гогранной проблематики, связанной с хроматическими числами.
43
Желая воодушевить заинтересованного читателя на самостоятель-
ные исследования, мы укажем в заключение ещё на две близких
постановки задачи о раскрасках пространств.
Определим две величины: ?( n , a1 , ..., ak ) и ?( n , A ). Число
?( n , a1 , ..., ak ) — это минимальное число цветов, в которые можно
так раскрасить все векторы в n-мерном пространстве, чтобы векто-
ры, отстоящие друг от друга на одно (любое) из расстояний ai >0,
i=1, 2, ..., k, оказались раскрашенными в разные цвета. Величи-
на ?( n , A ) — это наименьшее количество красок, необходимых
для такой раскраски n , при которой точки одного цвета не могут
образовывать множество A . Ясно, что обе введённые величины
напрямую обобщают понятие обычного хроматического числа. Изу-
чение этих величин дало ряд прекрасных результатов. Например,
на плоскости первая из них может быть, за счёт надлежащего
v
выбора чисел a1 >0, ..., ak >0 в качестве критических расстоя-
ний, сделана больше, чем ck ln k (c>0 — некоторая постоянная).
С ростом размерности она также ведёт себя принципиально по-дру-
гому, нежели чем величина ?( n ). Мы уже не станем вдаваться
здесь в какие-либо подробности и скажем только, что нерешённых
проблем относительно ?( n , a1 , ..., ak ) и ?( n , A ) ещё больше, чем
для классического хроматического числа.

ЛИТЕРАТУРА
[1] Р а й г о р о д с к и й А. М. Проблема Борсука и хроматиче-
ские числа метрических пространств // Успехи мат. наук. —
2001. — Т. 56. — Вып. 1. — С. 107—146.
[2] Х а р а р и Ф. Теория графов. — М.: Мир, 1973.
[3] С к в о р ц о в В. А. Примеры метрических пространств. —
М.: МЦНМО, 2002. — (Серия: <Библиотека ,,Математическое
просвещение“>. Вып. 16).
Рис. Ц1 Ц в е т а:
Рис. Ц2 Ц в е т а:
Желая сделать максимально на-
глядными раскраски плоскости и трёх-
мерного пространства, которые мы
обсуждали в начале нашей брошюры,
мы предприняли попытку нарисовать
их. Разумеется, в двумерном слу-
чае с этим нет никаких проблем,
и на рис. Ц1, Ц2 мы видим раскраски
плоскости в девять и семь цветов соот-
ветственно.
В трёхмерной ситуации возникают
значительные трудности, преодолеть ко-
торые оказывается весьма непросто.
Действительно, как нарисовать мно-
гогранники Вороного, которые сами
по себе довольно сложно устроены,
да ещё раскрасить их по-разному так,
чтобы это было видно?
Справиться с такой задачей помо-
гает метод изображения пространства,
придуманный голландским художником
М. Эшером и реализованный для раскра-
сок, связанных с оценками хромати-
ческих чисел, М. Ю. Пановым. Метод
сводится к тому, чтобы оставить от мно-
гогранника только его <рёберный каркас>
(рис. Ц3—Ц6), а грани не изображать.
Ведь мы хотим одновременно наблюдать
несколько разноцветных многогранни-
ков по каждому из трёх пространствен-
Рис. Ц3
ных направлений, а этого проще всего




Рис. Ц4
Рис. Ц5


добиться, сделав стенки (грани) прозрачными. Тем самым, мы и за внешним видом
многогранника по его каркасу уследим, и во все стороны посмотрим.
Конечно, рис. Ц7—Ц10 выглядят всё равно крайне запутанно, но такова уж
природа проблемы. Скажем, на рис. Ц7 изображена раскраска 3 кубами. Как бы
сидя внутри одного из кубов, мы окидываем взглядом всю перспективу, и все
27 цветов нам хорошо видны. Аналогично обстоит дело с рис. Ц8—Ц10. На рис. Ц8
мы видим раскраску Сойфера в 21 цвет, на рис. Ц9 и Ц10 — раскраски Кулсона
в 18 и 15 цветов соответственно.




Рис. Ц6
Рис. Ц7 Ц в е т а:
Рис. Ц8 Ц в е т а:
Рис. Ц9 Ц в е т а:
Рис. Ц10 Ц в е т а:

<< Пред. стр.

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

ОГЛАВЛЕНИЕ

Copyright © Design by: Sunlight webdesign