Вероятностный подход к задачам о графах расстояний и графах диаметров

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

Оглавление
Введение

1 Реализация случайных графов графами расстояний

1.1 Введение и формулировки геометрических результатов

1.2 Постановка вероятностной задачи и формулировки соответствующих результатов

1.3 Доказательства геометрических результатов

1.3.1 Доказательство теоремы

1.3.2 Доказательства теорем

1.3.3 Доказательство теоремы

1.4 Доказательства вероятностных результатов

1.4.1 Доказательство теоремы

1.4.2 Доказательство теоремы
1.5 Обобщения вероятностных результатов
1.5.1 Пороговые вероятности для реализации графом расстояний в размерностях с? ^ 3
1.5.2 Пороговые вероятности для реализации графом расстояний в размерности й —
2 Реализация случайных графов графами диаметров в размерностях й = 2 и (1
2.1 Введение
2.2 Формулировки результатов
2.3 Доказательства результатов для случая й
2.3.1 Доказательство теоремы
2.3.2 Доказательство теоремы
2.3.3 Доказательство теоремы
2.3.4 Доказательство теоремы
2.3.5 Доказательство теоремы
2.3.6 Доказательство теоремы
2.4 Доказательства результатов для случая (I,

2.4.1 Доказательство теоремы
2.4.2 Доказательство теоремы
2.4.3 Доказательство теоремы
2.4.4 Доказательство теоремы
2.4.5 Доказательство теоремы
3 Реализация случайных графов графами диаметров в размерности d ^ 4
3.1 Введение и формулировки результатов
3.2 Верхние оценки
3.2.1 Доказательство теоремы
3.2.2 Доказательство теоремы
3.3 Нижние оценки
3.3.1 Доказательство теоремы
3.3.2 Доказательство теоремы
3.4 Доказательство теоремы
3.4.1 Случай d — 4, р = const
3.4.2 Случай d > 4, р = const
3.5 Проблема со случаем р —»
Заключение
Список литературы

Введение
Настоящая работа стоит на стыке двух дисциплин: вероятностной комбинаторики и дискретной геометрии. Ниже мы расскажем о ключевых задачах каждой из них.
Дискретная геометрия как наука оформилась па рубеже Х1Х-ХХвв. Одним из ее основоположников можно считать Мпнковского (см. [53]), который исследовал расположение целочисленных векторов по отношению к выпуклым телам в пространстве и доказал фундаментальную теорему о выпуклом теле. Столь же значимые результаты в этой теме получили Вороной], Коркин, Золотарев (см. [2,47]) и другие. Сейчас это отдельный раздел теории чисел и геометрии, называемый геометрией чисел (см. [3,51]).
С геометрией чисел тесно связано еще одно направление дискретной геометрии. К этому направлению прежде всего относятся следующие три задачи. Первая — классическая задача Ньютона о плотнейшей упаковке шаров в пространстве (см. [5,22,24]). Вторая задача, двойственная к первой, это задача о редчайшем покрытии пространств шарами. Наконец, третья задача, о контактном числе — наибольшем количестве шаров, касающихся данного шара в пространстве (см. [8,61]).
Еще одно направление исследований в дискретной геометрии было инициировано Клейн, Эрдешем и Секерешем в 1934 году, которые доказали существование такого числа Аг(п), что среди любых N точек общего положения на плоскости найдется выпуклый п-уголышк (см. [6,41,42,44,55]).
Следующий класс проблем дискретной геометрии также предложен Эрдешем. Первый вопрос, который был им поставлен, — о наибольшем числе единичных расстояний в множестве из п точек па плоскости и в пространстве (см. [38]). Второй, не менее важный, наоборот, о числе различных расстояний в таком п-точечном множестве (см. [34,57]).
Все перечисленные выше задачи исключительно важны для дискретной геометрии, однако необходимо выделить еще две проблемы, которые имеют особенное значение для нашей работы и также носят фундаментальный характер. Первая из них это гипотеза Борсука о разбиении множества на части меньшего диаметра (см. [33]). Вторая — задача Нелсона- Эрдеша-Хадвигера о

Теперь рассмотрим случай т ^ Здесь воспользуемся оценкой С’^т_ ^ С[п ^ (£)т ^ (е1пк)т. Тогда

Е" = Е Е
■"=йЬ ,=
А- т-
^ ^ 8к2п~т2т(е21п2 к)тпате^-п'а ^
т=Юь г=
о о (г> 2 Он2 к)пае^ т ^ (, 3о 9 (1и2/г)пае2їїя'
^ 2^ &тк ( 2е ^ 22 8 I к2е
п ! п
~ 1и к
Как и в случае с > достаточно показать, что выражение в скобках стремится к нулю с ростом п. Первая его часть ограничена, поскольку к ^ к * —> 1. Рассмотрим вторую часть и подставим в экспоненту выражение
для к:
2п . 1 / к о , ((2 — 2а — е)папп
( к)п ехР < (1п п)пй ехр — J =
= (1п2 п)п“-1П1_в-5 = (1п2п)п“2.
Последнее выражение стремится к нулю при любом положительном £, что и доказывает теорему.
2.4 Доказательства результатов для случая <
Заметим, что если в графе диаметров в М3 число вершин к, то в нем не больше 2к — 2 ребер (см. [34]).
2.4.1 Доказательство теоремы
Хорошо известно, что при ограничениях нар, заданных в формулировке теоремы, случайный граф с асимптотической вероятностью 1 является уницик-лическим. Но индуцированный подграф такого графа на любых к вершинах и с любым к € (1,..., те} сам является унпциклическим, то есть, в частности, имеет хроматическое число не больше трех. Значит, при достаточно больших п п всех к
Р„р (З Я = (И7, Я) С С : \¥ = к, Н = С[ш,
Я — граф диаметров, у (Я) = 4) <