Экстремальные свойства дистанционных графов

• Автор: Рубанов, Олег Игоревич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 68 с. : ил.

Содержание
Обозначения
Введение

1 История вопроса и формулировки результатов

1.1 История вопроса

1.2 Нижние оценки хроматических чисел трёхмерных графов

расстояний с запретами на клики

1.3 Нижние оценки хроматических чисел графов расстояний с

запретами на клики в растущей размерности

1.3.1 Результаты с одним запрещённым расстоянием

1.3.2 Сравнение оценок СсПЧие(^) в теоремах 4, 5, 6 и 7

1.3.3 Результаты с несколькими запрещёнными расстояниями
1.3.4 Таблицы результатов теоремы
2 Хроматические числа трёхмерных графов расстояний без тетраэдров и треугольников
2.1 Доказательство теоремы
2.2 Доказательство теоремы
2.2.1 Основная часть доказательства теоремы
2.2.2 Доказательство предложения 2
2.2.3 Построение графа Т «шевелением»: вспомогательные
леммы
2.2.4 Процедура «шевеления»

3 Асимптотика хроматических чисел графов расстояний с несколькими запрещёнными расстояниями и без больших клик
при росте размерности пространства
3.1 Доказательство теоремы
3.2 Доказательство теоремы
3.3 Доказательство теоремы
3.4 Небольшой комментарий к теореме
3.5 Решение экстремальной задачи
Список литературы

Обозначения
• Ж‘ — п-мерное евклидово пространство
• (х, у) — скалярное произведение векторов X и у
• |х|, А — Х — модуль вектора х, А~к
• Ш — вектор из начала координат в точку X
• ЕК — математическое ожидание случайной величины V
• P(Z) — вероятность события Я.
• 1 — глава
• 1.2 — раздел 2 главы
• 1.2.3 — пункт 3 раздела 2 главы

Мозеровских веретён относительно осей, проходящих через пары точек А, Л3 И А2, /І4, и небольшим перебором.
Теорема доказана. Добавим, что полученный граф имеет 19 вершин и 44 ребра.
2.2 Доказательство теоремы
2.2.1 Основная часть доказательства теоремы
В нашей конструкции в качестве одной из составных частей мы будем использовать модификацию графа расстояний, построенного П. О’Доннеллом и Р. Хохбергом (см. [4], сам граф изображён на рисунке 1.2). Мы обозначим его Т> (см. рисунок 2.4).
ы) Аі Л
Все отмеченные здесь точки, обозначенные строчными буквами, представляют вершины, а отрезки и дуги, как сплошные, так и пунктирные, которые их соединяют, представляют рёбра. Граф состоит из 4-цикла {А, А2, Аз, УІ4} и 5-циклов ГД, Ні и Е2, которые представлены сплошными линиями, а также нескольких рёбер, которые проведены между этими циклами.
Лемма 1. Хроматическое число графа, изображённого на рисунке 2.4, равняется четырём. Кроме того, он не содержит треугольников.
Доказательство. Утверждение об отсутствии треугольников очевидно. Достаточно заметить, что граф состоит из 4-цикла {Аі, А2, Аз, АД и 5-циклов