Предельные распределения характеристик случайных дистанционных графов

• Автор: Ярмухаметов, Андрей Ринатович
• Шифр специальности: 01.01.05
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 63 с. : ил.

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

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

1.1 Основные определения и история задачи

1.2 Постановка основной задачи

1.3 Формулировки результатов

2 О связности случайного дистанционного графа

2.1 Доказательство пункта б) теоремы

2.2 Схема доказательства пункта а) теоремы

2.3 Доказательства утверждений 2.2, 2.3, 2.4, 2

2.3.1 Доказательство утверждения

2.3.2 Доказательство утверждения
2.3.3 Доказательство утверждения
2.3.4 Доказательство утверждения
2.3.5 Доказательство утверждения
3 О распределении количества древесных компонент в случайном дистанционном графе
3.1 Вспомогательные утверждения и леммы
3.1.1 Формулировки вспомогательных утверждений
3.1.2 Доказательство утверждения
3.1.3 Доказательство утверждения
3.1.4 Формулировка и доказательство леммы
3.1.5 Формулировка и доказательство леммы
3.1.6 Доказательство утверждения
3.1.7 Доказательство утверждения
3.1.8 Доказательство утверждения
3.2 Доказательство теоремы
3.2.1 Доказательство пункта 1
3.2.2 Доказательства пунктов 2 и
3.2.3 Доказательство пункта 3

3.2.4 Доказательство пункта
4 О гигантской компоненте в случайном дистанционном графе
4.1 Вспомогательные утверждения и леммы
4.1.1 Формулировки вспомогательных утверждений и лемм
4.1.2 Доказательство утверждения
4.1.3 Доказательство утверждения
4.1.4 Доказательство утверждения
4.1.5 Доказательство утверждения
4.1.6 Доказательство утверждения
4.2 Завершение доказательства пункта б) теоремы
4.3 Доказательство пункта а) теоремы
4.3.1 Ветвящиеся процессы
4.3.2 Завершение доказательства пункта а) теоремы
4.4 О предельной вероятности связности внутри фазового перехода
4.4.1 Доказательство теоремы

Введение
Открытие того, что детерминированные утверждения могут быть доказаны с помощью вероятностных соображений, позволило уже в первой половине XX в. установить ряд замечательных фактов из анализа, теории чисел, комбинаторики и теории информации. Вскоре стало ясно, что метод, который сейчас называется вероятностным, является весьма мощным инструментом получения результатов в дискретной математике.
Одним из тех, кто первым применил данный метод к задачам экстремальной комбинаторики, был венгерский математик Т. Селе. С помощью вероятностных соображений он доказал, что существует турнир на п вершинах, который содержит не менее п!/2"-1 гамильтоновых путей (1943, [1]). Селе не построил явную конструкцию такого турнира, но показал, что множество турниров, удовлетворяющих данному требованию, не пусто. Это является характерной чертой такого способа доказательств. Именно поэтому этот метод также называется неконструктивным.
Широкое применение метода к теории чисел привело к появлению вероятностной теории чисел ([2] — [3]). Одним из первых применений неконструктивного метода к данной отрасли математики было новое, более простое доказательство теоремы Г. Харди и С. Рамануджана (1917, [4]), принадлежащее П. Турану (1934, [5]).
Примечательно, что примерно в это же время в вычислительной математике стремительно развивается применение статистических методов испытаний, более известных под названием “Метод Монте-Карло” (1949, [6]). Статистические методы вычислений использовались еще в XVIII - XIX вв. Самым широкоизвестным таким методом, в том или ином виде входящем во многие университетские учебники по теории вероятностей, является метод определения числа 7Г с помощью бросания иглы Бюффона (например, [7]).
Наибольшее применение вероятностный метод получил в экстремальной теории множеств, а также в теории графов и гиперграфов. Одним из первых результатов в этих областях была теорема П. Эрдеша, Ч. Ко и Р. Радо (1938, [8]) об экстремальных свойствах совокупностей подмножеств конечного множества. Именно выдающийся венгерский математик Эрдеш считается

3.1.7 Доказательство утверждения
Имеем
М(к,г,М)= 1 = Мі-М2,

1 < (1) < <](т) <Ткіп
V 1 < и < V < г : У(т(к,,?(«))) П У(т(/г,(г;)))
м, = 1,
1<7'(1 )<-<]{г)<Тк

Очевидно, что
1<](1)<...<](г)<Тк,„
З 1 < и < и < г : У(т(к, ]{и))) П V" (т(/с, 37 (г?)))
Мг — (Тк,м)г ~ {Тк,мУ ,
м2< £ £ !-
1<и<и<Г 1 < ;(1) < ... < ](т) < Тк,н
У(т(к,](и))) ПУ(тЦ,;(»))) # В
Если при некоторых 1 и 12 имеем 1 < 1 < 12 < и И(т(£Д1)) П
У(т(к,12)) 0, то очевидно, что
У(т(к,11))иУ(т(к,12))<2к-1.
Следовательно,
. Г2 ( .г-2 лг2/г-1 2 Гт у (А;!)2 Л*"1
м2 < СГ (Д,лг) '/V = Сг'(Д|ЛГ) —2
Т1, ~4 ТУ2“2
ж*)* _ 0(Мі),

/с2/с-4 ’ 2/21п 2/ АУ2/г
Таким образом, утверждение 3.4 доказано.
3.1.8 Доказательство утверждения
Из утверждения 3.3 следует, что
Е (Хм,кУ = £ 1) А"дг (г))
1 <Д1) < ... <Дг) <тк,„
V 1 < и < 1/ < г : У(т(А:,<;(и))) П У(т(к, ,?(и)))
(3.13)