Оглавление
Обозначения 5
Введение 6
1 История вопроса, постановки задач и формулировки результатов 9
1.1 Оценки хроматических чисел пространств (Мп, и У при
запрете одного и нескольких расстояний........................ 9
1.1.1 Постановки задач....................................... 9
1.1.2 Известные безусловные результаты.......................12
1.1.3 Известные условные результаты..........................14
1.1.4 Новые безусловные результаты...........................15
1.1.5 Новые условные результаты..............................17
1.2 Оценки хроматических чисел пространств (1К'\ /і) и 1г) при
запрете одного и нескольких расстояний........................18
1.3 Изменение нижней оценки величины х(^п>/?; {«}) при „непрерывном“ изменении метрики ОТ 1\ к І2...............................20
1.3.1 Известные результаты...................................20
1.3.2 Метрика рг ............................................21
1.4 Условные нижние оценки величины хк(^п5 У {&}) и числа Борсука ..............................................................22
2 Доказательства теорем 7 и 8 24
2.1 Переформулировки задач на языке теории графов................24
2.2 Основные шаги доказательства теорем 7 и 8..................26
2.3 Оптимизация оценок из раздела 2.2..............................32
2.3.1 Асимптотика для суммы, дающей верхнюю оценку числа независимости графа 33
2.3.2 Асимптотика для суммы, дающей верхнюю оценку числа независимости графа б?2 35
2.3.3 Асимптотики нижних оценок хроматических чисел графов Сі,(?2 и завершение доказательств теорем 7, 8 ... 36
2
3 Доказательства оптимальных нижних оценок величины
13 случае к > 3 39
3.1 Метод получения оценок. Экстремальная задача...................39
3.2 Численные результаты. Оценки хроматических чисел..............43
4 Доказательства новых условных оценок хроматических чисел и комментарии к ним 45
4.1 Доказательства теорем 9 - 11................................ 45
4.1.1 Доказательства теорем 9, 11 45
4.1.2 Доказательство теоремы 10..............................49
4.2 Комментарии к доказательствам теорем 9-11.....................51
4.2.1 Несколько замечаний ...................................52
4.2.2 Общий подход к получению условных оценок...............53
5 Доказательство нижней оценки величины хк(^п 5 ^15 2) 55
5.1 Доказательство теоремы 14.....................................55
5.2 Получение нижних оценок величины 5£й(®п> к) в случае к > 3 58
6 Изменение нижней асимптотической оценки при „непрерывном“ изменении метрики ОТ К 12 61
6.1 Описание метода решения задачи и основная лемма...............61
6.2 Формулировка экстремальной задачи.............................63
6.3 Решение экстремальной задачи..................................65
6.4 Практическая реализация алгоритма и новые результаты .... 67
7 Доказательство условных оценок величины М) и числа Борсука 70
7.1 Доказательство теоремы 15.....................................70
3
Ч I
Обозначения
• 1 — глава 1
• 1.2 — раздел 2 главы 1
• 1.2.3 — параграф 3 раздела 2 главы 1
• (Rn, 12) — евклидово пространство со стандартной метрикой
• (<Г,Ь) — пространство векторов с рациональными координатами с евклидовой метрикой
• (RnJi) — евклидово пространство с метрикой где
*l(x>y) = 1*1 - »il +-1- l*n - »n|
• (QVi) — пространство векторов с рациональными координатами с метрикой її
• < х,у > — скалярное произведение векторов в (Кт\/2)
• х * у — прямое произведение векторов
• а(п) х Ь(п) — существуют такие константы ci,c2 > 0, что при всех п выполнено с\Ь(п) < а{п) < с26(п)
• В записях вида
XsSRnM\k) > {const “Ь o(l))n.
будут появляться различные значения константы const. Все они будут обозначаться Çk или
• В записях вида
xQ(QV2;A0>(& + o(l))n.
будут появляться различные значения константы const. Все они будут обозначаться & или
4
В записях и и да
Xr(Rn,h\k) > (к* + о(1))п.
будут появляться различные значения константы const. Все они будут обозначаться ас* или
5
Введение
В работе изучаются хроматические числа различных метрических пространств с к запрещенными расстояниями, т.е., минимальные количества цветов, в которые можно окрасить все точки пространства таким образом, что никакие две точки одного цвета не будут находиться на запрещенном расстоянии друг от друга.
Впервые задача отыскания хроматического числа была сформулирована в 1950 году Э. Нелсоном. В тот момент речь шла о хроматическом числе евклидова пространства с одним запрещенным расстоянием. Значительную роль в развитии науки о хроматическом числе сыграли Дж. Избелл, Г. Хадвигер, П. Эрдеш, М. Гарднер и братья Мозеры (см. [1, 2, 3, 4, 5]). История возникновения задачи о хроматическом числе освещена в обзоре А. Сойфера (см.
И).
До обсуждения произвольных метрических пространств дело дошло в 1976 году, когда М. Бенда и М. Перлес написали статью [7], в которой рассматривалось пространство векторов с рациональными координатами с евклидовым расстоянием в нем.
Развитие науки о хроматических числах шло одновременно по нескольким направлениям: множество результатов было получено в малых размерностях (см. [6, 8]). Параллельно с этим шла работа над асимптотическими верхними и нижними оценками. Первая нетривиальная (линейная) нижняя оценка хроматического числа евклидова пространства с одним запрещенным расстоянием была получена Д. Райским (см. [9]). Затем Д. Ларман, К. Роджерс, П. Эрдеш, В. Шош и Ж. Ііадь доказали квадратичную нижнюю оценку (см. [8, 10)). Позже П. Фраикл и Р. Уилсон получили экспоненциальное ограничение снизу для указанной величины (см. [11)). Л.М. Райгородскому принадлежит наилучшая на данный момент константа в нижней экспоненциальной оценке классического хроматического числа (см. [8]). Кроме того, им были получены общие верхняя и нижняя экспоненциальные оценки для произвольного числа запрещенных расстояний (см. [12,13]). Наилучшая верхняя оценка для одного запрещенного расстояния была доказана Ларманом и Роджерсом
6
- Київ+380960830922