Комбинаторные и вероятностные методы в задаче о геометрических числах Рамсея

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

Оглавление
Введение
Теория Рамсея
Комбинаторная и дискретная геометрия
Вероятностный метод
1 История задачи и результаты
1.1 История задачи
1.2 Формулировки результатов
2 Доказательства теорем 4-7 о нижних оценках дистанционного числа Рамсея в случаях плоскости и трехмерного пространства
2.1 Вспомогательные утверждения
2.1.1 Вспомогательные утверждения для теорем 4 и
2.1.2 Вспомогательные утверждения для теорем 6 и
2.1.3 Локальная Лемма Ловаса
2.2 Доказательство теоремы
2.3 Доказательство теоремы
2.4 Доказательство теоремы
2.5 Доказательство теоремы
2.6 Одномерный случай
3 Доказательство теоремы 8 об оценках дистанционного числа Рамсея в случаях малых размерностей пространства
3.1 Задача о плотнейших упаковках
3.1.1 Постановка задачи
3.1.2 Определения из теории решеток и упаковок
3.1.3 Идеи получения нижних оценок тДМ")
3.1.4 Основные результаты в задаче о плотнейших упаковках .
3.2 Конструкция Крофта для Ж
3.3 Конструкция для Ж

3.4 Доказательство теоремы 15: результаты в задаче о плотнейших
множествах без расстояния единица
3.4.1 Доказательство теоремы 15 в случае п —
3.4.2 Доказательство теоремы 15 в случае п —
3.4.3 Доказательство теоремы 15 в случае п —
3.4.4 Доказательство теоремы 15 в случае п =
3.4.5 Доказательство теоремы 15 в случае п —
3.5 Доказательство теоремы
4 Доказательство теоремы 9 об оценке дистанционного числа Рамсея в случае растущей размерности пространства
4.1 Вспомогательная теорема об оценке сверху числа клик дистанционных графов
4.2 Доказательство вспомогательной теоремы
4.3 Доказательство основной теоремы 9 об оценке дистанционного
числа Рамсея
4.3.1 Получение нижней оценки Лмен(й, 5, с!)
4.3.2 Доказательство теоремы 9 в случаях й = 4,
4.3.3 Доказательство теоремы 9 в случаях Л ^
Заключение
Список литературы

Введение
Диссертация посвящена разработке вероятностной техники для получения результатов в классических задачах экстремальной комбинаторики, а также комбинаторной и дискретной геометрии. Прежде всего мы опишем круг задач, которыми мы занимаемся, а потом скажем о том вероятностном контексте, в который они вкладываются.
Теория Рамсея
Теория Рамсея — ветвь комбинаторики, появившаяся менее века назад и получившая стремительное развитие. Идеи и техника теории Рамсея связываются с такими разделами математики, как теория множеств, теория графов, комбинаторная теория чисел, теория вероятностей, анализ.
В общем виде, эта теория исследует следующий вопрос: если конкретная структура (алгебраическая, геометрическая, комбинаторная) произвольным образом разбивается на конечное количество классов, то наличие какого рода подструктур всегда можно гарантировать по крайней мере в одном из этих классов?
Особенности результатов в рамках теории Рамсея заключаются в том, что они имеют, как правило, неконструктивный характер, а также в том, что гарантия наличия тех или иных подструктур дается для структур с достаточно большим числом элементов (обычно, в экспоненциальной зависимости от размера подструктуры).
Теория получила название в честь английского математика и философа Фрэнка Рамсея, предложившего ее фундаментальную идею, а также доказавшего результат, впоследствии ставший известным как теорема Рамсея (см. [73]). Теорема утверждает, что при любой раскраске ребер достаточно большого полного графа всегда найдется одноцветный полный подграф с наперед заданным числом вершин.
Начиная с 1930 годов теория Рамсея стала активно развиваться и обрела популярность благодаря работам знаменитого венгерского математика Пола

Многогранником Вороного И7* решетки Ьп в Ж” для данной точки решетки а называется множество точек пространства Ж”, которые по меньшей мере так же близки к данной точке, как и к любой другой точке решетки:
1У£п = {х € Мп : |х - а| ^ |х - Ь| V Ь € 1п}.
3.1.3 Идеи получения НИЖНИХ оценок 7711 (М")
Простейший способ получения НИЖНИХ оценок 7771 (Ж") состоит в следующем. Рассмотрим решетку Ьп, на которой реализуется плотнейшая упаковка шаров радиуса г в Ж’1, и эту упаковку. Обозначим ее О(г). Пусть В*(г) — (открытый) шар в Ж” с центром в точке решетки а £ Ьп и радиусом г. Таким образом,
од = и в
а£2>п
Оставим центры шаров на месте, а радиус каждого шара уменьшим в два раза. Понятно, что в таком случае мы получим множество без расстояния г, которое равно диаметру новых шаров. При этом плотность полученного множества будет в 2П раз меньше, чем плотность изначальной упаковки Г1(г). В общем случае это и есть лучшая известная нижняя оценка величины т^М").
В случае плоскости плотность лучшей упаковки равна к, 0.9069. Таким образом, имеем:
гщ(Ж2) > = 0.2267.

Однако Крофт улучшает эту оценку, приводя пример множества, имеющего плотность 0.2293 ... (см. [20] и раздел 3.2).
Основной целью разделов 3.2-3.4 является построение как можно более плотных множеств без расстояния единица в Жп, п = 3,..., 8, за счет чего МЫ получим лучшие НИЖНИС оценки величины 777-1 (Ж71) при 77 = 3, . . . , 8.
3.1.4 Основные результаты в задаче о плотнейших упаковках Теорема 15. Имеют место следующие неравенства:
ттг! (Ж3) ^ 0.09877, 7тц(Ж6) ^ 0.00806,
7771 (Ж4) ^ 0.04413, 777,1 (Ж7) $5 0.00352,
77ц(М5) > 0.01833, 7771 (Ж8) ^ 0.00165.