Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/oim/stolymp/raigor08.ps Дата изменения: Fri Feb 22 14:37:50 2008 Дата индексирования: Mon Feb 4 12:10:15 2013 Кодировка: koi8-r Поисковые слова: arp 220

Хроматические числа и проблема Борсука
А.М. Райгородский
1 Хроматические числа
Назовем хроматическим числом евклидова пространства R n минимальное количество цветов, в ко-
торые можно так покрасить все точки R n , чтобы между одноцветными точками не было расстояния
1. Формально, хроматическое число { это величина
(R n ) = min
n
 : R n = V 1
G
: : :
G
V  ; 8 i 8 x; y 2 V i jx yj 6= 1
o
;
где jx yj { евклидово расстояние между векторами x; y 2 R n .
Задача отыскания хроматического числа пространства была поставлена Э. Нелсоном в 1950 году;
однако похожие вопросы предлагались и раньше. Во всяком случае усилиями Г. Хадвигера, П.
Эрдеша и др. задача превратилась в классическую проблему комбинаторной геометрии, и теперь
любое продвижение в ней вызывает огромный резонанс.
Об истории проблемы и о различных результатах, полученных в связи с ней, можно прочесть,
например, в [1], [2]. Мы не станем здесь вдаваться в детали, но приведем лишь самые яркие и,
одновременно, важные для дальнейшего факты.
Точное значение хроматического числа известно только в случае прямой: (R 1 ) = 2. Подлин-
ной трагедией (или, если угодно, позором) является отсутствие окончательного ответа на вопрос
Нелсона в размерности 2. Известно лишь, что 4  (R 2 )  7. В R 3 зазор в оценках еще ужаснее:
6  (R 3 )  15. Наконец, доказано, что
7  (R 4 )  49; (R 5 )  9:
Список подобных утверждений можно продолжать, но мы cкажем, что при n ! 1 имеют место
неравенства
(1:239::: + o(1)) n  (R n )  (3 + o(1)) n ;
и других оценок приводить не станем.
Перейдем к формулировкам упражнений и задач. Упражения, как правило, элементарны. Они
нужны, скорее, для того, чтобы читатель мог привыкнуть к проблеме. Гораздо интереснее задачи.
Упражнение 1. Докажите оценки a) (R 2 )  7; b) (R 2 )  4; c) (R 3 )  5; d) (R n )  n + 2 при
n  2; e) (R 3 )  27; f) (R n ) < 1.
Задача 1. Докажите неравенство a) (R 4 )  8; b) (R 5 )  10. Указание. Полезно прочесть
статьи [3], [4], [5].
Задача отыскания хроматического числа тесно связана с теорией графов. Назовем граф G =
(V; E) n-мерным дистанционным (или n-мерным графом расстояний), если
V  R n ; E  f(x; y) 2 V  V : jx yj = ag;
где a { произвольное фиксированное положительное число.
Назовем хроматическим числом графа G = (V; E) минимальное количество цветов (обозначим
его (G)), в которые можно так покрасить все вершины графа, чтобы между одноцветными точками
не было ребра. Иными словами,
(G) = min
n
 : V = V 1
G
: : :
G
V  ; 8 i 8 x; y 2 V i (x; y) 62 E
o
:
1

Скажем, что W  V { независимое множество вершин некоторого графа G = (V; E), если
никакие две вершины из W не соединены ребром. Обозначим через (G) количество элементов в
самом жирном независимом множестве вершин графа G. Это так называемое число независимости
графа:
(G) = maxfjW j : W  V; 8 x; y 2 W (x; y) 62 Eg:
Упражнение 2. Докажите, что если G { n-мерный дистанционный граф, то (R n )  (G).
Упражнение 3. Докажите неравенство (G)  jV j
(G)
, коль скоро G = (V; E).
Упражнение 4. Как устроены графы расстояний, с помощью которых получаются оценки a)
(R 2 )  4; b) (R 3 )  5; c) (R 3 )  6; d) (R 4 )  7; e) (R n )  n + 2?
Упражнение 5. Положим
V = fx = (x 1 ; : : : ; x n ) : x i 2 f0; 1g; x 1 + : : : +x n = 3g; E = f(x; y) 2 V V : jx yj = 2g; G = (V; E):
a) Найдите (G); b) докажите оценку (G)  cn 2 с каким-нибудь c > 0; c) вычислите константу c
из предыдущего пункта как можно аккуратнее.
Назовем обхватом графа G величину g(G), равную длине кратчайшего цикла в G.
Упражнение 6. Докажите, что для любого k существует граф с (G)  k и g(G) > 3 (граф с
большим хроматическим числом без треугольников).
В [6], [7] Н. Уормалд, П. О'Доннелл и Р. Хохберг построили двумерные дистанционные графы G,
имеющие довольно мало вершин и в то же время такие, что (G)  4, но g(G) > 3 (и даже > 4). В
свою очередь О. Рубанов в [8] описал конструкцию трехмерного дистанционного графа с (G)  5
и без тетраэдров.
Задача 2. Попытайтесь еще уменьшить количество вершин в конструкциях, подобных конструк-
циям Уормалда и О'Доннелла { Хохберга.
Задача 3. Найдите как можно лучшую нижнюю оценку числа вершин в конструкциях, подобных
конструкциям Уормалда и О'Доннелла { Хохберга.
Задача 4. Постройте трехмерный граф расстояний, у которого (G)  5 и который не содержит
треугольников.
Задача 7. Постройте трехмерный граф расстояний, у которого (G)  6 и который не содержит
тетраэдров.
Задача 8. Постройте трехмерный граф расстояний, у которого (G)  6 и который не содержит
треугольников.
Задача 9. Найдите конструкцию, подобную рубановской, с меньшим числом вершин или дока-
жите, что таких конструкций не существует.
Назовем последовательность положительных вещественных чисел a n лакунарной с коэффициен-
том лакунарности d 2 N , если an+1
an
 1 + 1
d
. Иными словами, последовательность лакунарна, если
она растет не медленнее некоторой геометрической прогрессии. Положим
(R n ; fa i g) = min
n
 : R n = V 1
G
: : :
G
V  ; 8 i 8 x; y 2 V i jx yj 62 fa i g
o
:
Таким образом, на сей раз мы запрещаем точкам одного цвета отстоять на любое расстояние из
множества fa i g.
2

Упражнение 7. Докажите, что для любого d существует такая лакунарная последовательность с
коэффициентом d, что (R 1 ; fa i g)  d + 1.
Задача 10. Верно ли, что найдется такая функция !(d) !1, d !1, с которой
max
fa i g
(R 1 ; fa i g)  d!(d)?
Здесь максимум берется по всем лакунарным последовательностям с коэффициентом d.
2 Проблема Борсука
Эта задача также является классической в области комбинаторной геометрии. Она была поставлена
К. Борсуком в 1933 году, и про нее можно прочесть, например, в [2], [9], [10].
Сформулируем проблему. Для ограниченного
множества
 R n положим
diam
= sup
x;y2

jx yj:
Введенная величина называется диаметром
множества
Определим
f(
как минимальное коли-
чество частей меньшего диаметра, на которые можно разбить данное
Пусть, наконец, f(n) =
max


f(
5 где максимум берется по всем ограниченным множествам в пространстве. Таким обра-
зом,
f(n) =
max
min
n
f
:
=
1
G
: : :
G
f ; 8 i
diam
i <
diam

o
:
Иными словами, f(n) { это минимальное число частей меньшего диаметра, на которые можно раз-
бить произвольное множество в R n . Назовем его числом Борсука.
Упражнение 8. Докажите, что f(n)  n + 1.
Упражнение 9. Докажите, что для сферы S n 1  R n выполнено f(S n 1 )  n + 1.
Упражнения 8 и 9 являются той самой мотивировкой, за счет которой Борсук высказал гипотезу:
f(n) = n + 1. Как ни странно, гипотеза неверна! О контрпримерах можно прочесть в [2], [9]. Все
эти контрпримеры основаны на построении некоторых множеств "(0,1)-векторов", подобных тому,
которое рассматривалось в упражнении 5. К сожалению, в настоящее время гипотеза опровергнута
лишь в размерностях n > 297. При этом в размерностях n  3 гипотеза справедлива. Случай n = 1
тривиален (убедитесь в этом!), случаи же n = 2; 3 подробно изучены в [10]. Что происходит при
n 2 [4; 297], никто до сих пор не знает.
В связи с известной технологией построения контрпримеров, возникает следующая комбинатор-
ная задача.
Задача 11. Пусть n = 2k,
V = fx = (x 1 ; : : : ; x n ) : x i 2 f1; 0; 1g; jfi : x i = 1gj = kg:
Рассмотрим произвольное множество
W = fx 1 ; : : : ; x s g  V;
предполагая, что скалярное произведение
(x; y) = x 1 y 1 + : : : + x n y n
любых двух его элементов не равно нулю. Иными словами, W { это произвольное подмножество
V , состоящее из попарно неортогональных векторов. Насколько большим может быть s = jW j?
Указание. Поработайте сперва с n = 4; 6; 8; 10; 12.
3

Подобно тому, как при изучении хроматических чисел были полезны графы расстояний, при
работе с числом Борсука нужны графы диаметров. Пусть дано
множество
 R n ,
diam
< 1.
Назовем граф
G
=(
; E) графом диаметров этого множества, если
E = f(x; y)
2

: jx yj =
diam
g:
Упражнение 10. Убедитесь в том, что для конечных
множеств
выполнено
f(
=
(G
).
Упражнение 11. Приведите пример (замкнутого)
множества
для которого
f(
6=
(G
).
Упражнение 12. Покажите, что
если
 R 2 и
j
j = n, то в
G
не более n ребер.
Проблема Борсука нетривиальна даже в случае так называемых двухдистанционных множеств.
Назовем
множество
 R n двухдистанционным, если расстояния между его точками принимают
всего два различных значения, большее из которых, естественно, является диаметром.
Задача 12. Какова максимальная мощность двухдистанционного множества в R n ? Ответ следует
искать в виде функции от n. Однако интересны и частные результаты при конкретных значениях
n.
Задача 13. Какова максимальная мощность двухдистанционного множества в R n , коль скоро от-
ношение большего из двух расстояний к меньшему полагается равным некоторому a? Ответ следует
искать в виде функции от n и a. Однако интересны и частные результаты при конкретных значе-
ниях n и a.
Задача 14. Верна ли гипотеза Борсука для двухдистанционных множеств при каком-нибудь n >
3?
Задача 15. Верна ли гипотеза Борсука для двухдистанционных множеств при каком-нибудь n > 3
и каких-нибудь a (см. задачу 13)?
В работе [11] гипотеза Борсука доказана для произвольных наборов (0,1)-векторов при всех
n  9.
Задача 16. Докажите гипотезу Борсука для произвольных наборов (-1,0,1)-векторов при всех
достаточно малых n. Здесь, в идеале, n  9.
Задача 17. Докажите гипотезу Борсука для произвольных двухдистанционных множеств (0,1)-
векторов при всех достаточно малых n. Разумеется, в данном случае интересны только n > 9.
Задача 18. Докажите гипотезу Борсука для произвольных двухдистанционных множеств (-1,0,1)-
векторов при всех достаточно малых n. Тут уже любопытны и n  9.
Замечание 1. На конкурс принимаются решения любых задач (даже одной может быть доста-
точно!), а также упражнений 4 с), d), 5, 6, 9, 11, 12 (они сравнительно нетривиальны).
Замечание 2. Я всегда готов помочь с отысканием цитированной литературы!
4

Список литературы
[1] А.М. Райгородский, Хроматические числа, Москва, МЦНМО, 2003.
[2] А.М. Райгородский, Линейно-алгебраический метод в комбинаторике, Москва, МЦНМО, 2007.
[3] O. Nechushtan, On the space chromatic number, Discrete Mathematics, 256 (2002), 499 - 507.
[4] Л.Л. Иванов, Оценка хроматического числа пространства R 4 , Успехи матем. наук, 61 (2006),
N5, 371 - 372.
[5] D.G. Larman, C.A. Rogers, The realization of distances within sets in Euclidean space, Mathematika,
19 (1972), 1 - 24.
[6] N. Wormald, A 4-chromatic graph with a special plane drawing, J. Austral. Math. Soc. Ser. A, 28
(1979), N1, 1 - 8.
[7] R. Hochberg, P. O'Donnell, Some 4-chromatic unit-distance graphs without small cycles, Geombina-
torics, 5 (1996), N4, 137 - 141.
[8] О. Рубанов, Хроматические числа трехмерных графов расстояний, не содержащих тетра-
эдров, Матем. заметки, 82 (2007), N5, 797 - 800.
[9] А.М. Райгородский, Проблема Борсука, Москва, МЦНМО, 2006.
[10] В.Г. Болтянский и И.Ц. Гохберг, Теоремы и задачи комбинаторной геометрии, Москва, "На-
ука", 1965.
[11] G.M. Ziegler, Coloring Hamming graphs, optimal binary codes, and the 0/1 - Borsuk problem in low
dimensions, Lect. Notes Comput. Sci., 2122 (2001), 159 - 171.
5