Упаковки и раскраски сфер в многомерных пространствах

• Автор: Купавский, Андрей Борисович
• Шифр специальности: 01.01.06, 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 88 с. : ил.

Оглавление
Введение
1 Раскраски сфер и хроматические числа пространств малой
размерности
1.1 Хроматическое число
1.2 Оценка величины х(®9)
1.2.1 Вывод теоремы 1 из теоремы 2 и новая оценка х(®10) • • Ю
1.2.2 Доказательство теоремы
Оценка а(С?) >
Оценка а(С) < 12: вспомогательная лемма
Доказательство оценки а (С) <
1.2.3 О верхней оценке хроматического числа графа С
1.3 Поднятие оценок в большую размерность
1.3.1 Доказательство теоремы 5: вспомогательные леммы
1.3.2 Завершение доказательства теоремы
1.4 Пестрота сфер
1.4.1 Одномерный случай
Вводное замечание и вспомогательные утверждения
Доказательство теоремы
1.4.2 Двумерный случай
Доказательство теоремы
Доказательство теоремы
1.4.3 Многомерный случай
Основная конструкция
Доказательство теоремы
Доказательство теоремы
Доказательство теоремы
Возможные дальнейшие результаты

2 Разбиения трехмерных множеств на части меньшего диаметра
2.1 Универсальные покрывающие системы
2.2 Построение УПС
2.3 Построение разбиения
2.4 Отыскание диаметров частей при б > 0.
2.4.1 Простейшие наблюдения
2.4.2 Редукция к одномерным составляющим границ
2.4.3 Редукция к нульмерным составляющим границ
2.4.4 Окончательная локализация диаметров
2.4.5 Сводка вычислений
2.4.6 Выбор параметров и завершение вычислений
2.5 Отыскание диаметров частей при с! < 0.
3 Асимптотические оценки хроматического числа пространства
и упаковки выпуклых центрально-симметричных тел
3.1 Хроматическое число
3.2 Доказательство теоремы
Список литературы

Введение
Данная диссертация состоит из трех глав, В первой главе мы изучаем раскраски сфер и хроматические числа пространств малой размерности. Вторая глава посвящена разбиениям трехмерных множеств. В третьей главе идет речь об асимптотических оценках хроматических чисел пространств и упаковках выпуклых центрально-симметричных множеств.
Задача о хроматическом числе пространства — это одна из классических задач комбинаторной геометрии (см. [18], [34]). В 1950 году Нелсон поставил следующий вопрос: Какое минимальное число цветов х(®^2) требуется для покраски точек плоскости, чтобы не было пары одноцветных точек на единичном расстоянии? Величина х(М2) называется хроматическим числом плоскости. Аналогичный вопрос можно задать и в больших размерностях. Формально говоря, хроматическое число пространства — это величина
Х(М'г) = min <|?n : R" = |^J V,. V? = 1,.... т /х. у £ V, х — у ф l| .
За прошедшие 60 лет было получено множество результатов касательно хроматического числа пространства. Франклом и Уилсоном [40] и Ларманом и Роджерсом [50] было доказано, что хроматическое число пространства растет экспоненциально с ростом размерности. Были найдены многочисленные оценки хроматического числа в малых размерностях (см. работы [16], [35], [50], [56] и др.). Кроме того, изучались различные обобщения задачи об отыскании хроматического числа пространства (см. [16], [26], [31], [62]). Например, в работе [31] была в общем виде сформулирована задача о нахождении хроматического числа произвольного метрического пространства. Также изучалось измеримое хроматическое число, которое определяется аналогично обычному хроматическому числу, но при этом требуется, чтобы множества точек одного цвета были измеримыми (см. [30], [39]). Наконец, изучались хроматические числа пространств с множествами запрещенных расстояний (см. [2], [19], [26]). Однако, до сих пор непонятно, чему равняется хроматическое число плоскости: известны лишь оценки 4 < х(®2) Д ?•

угольник с высотой к, опущенной из вершины С на основание АВ. Пусть при этом величина к подобрана так, что является радиусом окружности, в которую можно вписать цикл нечетной длины, каждое ребро которого имеет единичную длину. Мы добиваемся этого за счет подбора длины отрезка АВ. Возможность такого выбора нам гарантирует лемма 2. Мы можем применить ее в данной ситуации, поскольку |/&| может принимать любое значение в интервале (0,2г), а диаметр 5*, равный 2г, больше 1/2. Применяя лемму 3, будем считать, что отрезок АВ разноцветный. Далее, вращаем пространство М3 вокруг АВ. При этом С описывает окружность, в которую можно вписать цикл нечетной длины, и которая, следовательно, покрашена не менее чем в три цвета. На этой окружности лежит точка И, покрашенная в цвет, отличный от цветов А я В. Точки Л,1?,.0 образуют трехцветный треугольник, вписанный в окружность радиуса г. Таким образом, утверждение пункта 4 доказано.
Пункт 5. Пусть п = 3.
Как мы и обещали, мы приведем только план доказательства. Вписываем последовательно в Д1 точки А,Р,(^,В, так, что |ЛР| = РС} — |<Э-В| = 1. Применяя лемму 3, можно без ограничения общности считать, что А и В разного цвета. Далее, по лемме 2, существует счетное всюду плотное подмножество радиусов и С (1/2, оо), таких, что в окружность 53, с радиусом г1 Е и можно вписать цикл нечетной длины с единичными ребрами. Повторив вычисления, проводимые в параграфе 1.3.1, нетрудно убедиться, что при г Е 1 7з) ^ (тз’ ^2 + Щ расстояние г' от точки Р до прямой
АВ больше 1/2, поэтому существует счетное всюду плотное множество и, и С и л/2 + л/з), такое, что, если г Е II, то в 5/, можно
вписать цикл нечетной длины.
Зафиксируем г Е и. Вращаем пространство вокруг АВ. При этом Р опишет окружность 5/. Впишем в нее цикл нечетной длины и выберем ребро РР2-, покрашенное не в цвет вершины В. Два конца этого ребра - это образы точки Р при некоторых поворотах пространства. Применим эти повороты к С/. Получим две вершины 6Д, (32• Одна из них, допустим <2!, покрашена не в цвет А. Тогда вершины А, Р, (^1, В покрашены в разные цвета.
1.4.2 Двумерный случай
В этом параграфе рассмотрены двумерные сферы. Пользуясь результатами, описанными в этом параграфе, мы, в частности, получим другим способом оценку х(К4) > 7 и докажем оценку х(1К12) > 27.