Экстремальные характеристики вложений случайных графов в геометрические графы

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

Общая характеристика работы

Глава 1: Постановка задачи и формулировки результатов

1.1 Определение и свойства случайных графов

1.2 Несколько слов о проблеме Нелсона - Эрдеша

- Хадвигера

1.3 Трудность проблемы Нелсона - Эрдеша - Хадвигера

1.3.1 Интерпретация задачи в терминах случайного графа

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

1.4 Комментарии

Глава 2: Доказательство теоремы 3
2.1 Основная часть доказательства теоремы
2.1.1 Предварительные рассуждения
2.1.2 Неравенство Азумы
2.1.3 Нижняя оценка математического ожидания величины
Ут4+1
2.1.4 Завершение доказательства теоремы 3
2.2 Доказательство леммы
2.2.1 Предварительные рассуждения

2.2.2 Асимптотика для М|1У|
2.2.3 Завершение доказательства леммы

Глава 3: Доказательство теоремы 4
3.1 Основная идея
3.2 Отыскание змеев в случайных графах
3.3 Оценка математического ожидания
3.4 Оценка второго момента и завершение доказательства теоремы

Теория случайных графов - это современный и бурно развивающийся раздел комбинаторной теории вероятностей, который появился в середине XX века и за прошедшие десятилетия оформился в многогранную и глубоко проработанную самостоятельную дисциплину. В основе теории лежит очень важная идея, состоящая в том, что мощные методы теории вероятностей должны существенно помочь исследованиям свойств графов, дать принципиально новый ракурс для рассмотрения классического комбинаторного объекта. И действительно, зачастую нам интересно знать, с какой ’’степенью достоверности” выполнено то или иное свойство графа: скажем, граф, скорее, связен, или же, напротив, более правдоподобно предположение о его несвязности. Разумеется, строгий смысл в понятие достоверности вкладывается именно с помощью вероятности.
Серьезным стимулом развития теории случайных графов как самостоятельного раздела теории вероятностей стала и та роль, которую случайные графы играют в различных приложениях. Здесь можно говорить и об алгоритмических аспектах теории графов, и о применении моделей случайного графа для статистического анализа различных сложных сетей - в том числе социальных, биологических и пр. (см. [1], [2], [3]). Во всяком случае на нынешнем этапе своего становления наука о случайных графах имеет как значительную теоретическую, так и огромную практическую составляющие.
Систематическое изучение случайных графов было инициировано П. Эрдешем и А. Реньи, которые предложили про-

2.2.3 Завершение доказательства леммы
Асимптотическая оценка М|ИД найдена, таким образом, возникают две принципиально различных ситуации: первая ситуация соответствует пунктам 1 и 3 из леммы (в ее рамках мы показали, что М|ИД = ^д(2)(1 + 5і(т)), где <5і(т) — о(1), т —* оо); вторая ситуация соответствует пунктам 2 и 4 из леммы (в ее рамках мы показали,что М|ИД < |С'д(с1 + 1)).
Ситуация 1. Для дальнейшего нам удобно выразить М|ИД через
Я Г X
1т,сЙ
(см. пункт 2.2.1). Итак,
мхтМ 2 - Сі+2рс^
Мт = ±д(2)(1 + 61(т))
= + «»))
_ 1(-«г+2 — — 2)! 2С1+,-1/'-| , т / _
1 л+2 (о? + 2)2(с? + 1)2(т — (I — 2) ... (т — 2с1 — 1) ~ 2 т 2(о? + 2)!
•р2(-^+2_1(1 + 5і(т))
г (^ + 2)2(с?+1)2тгі+2 2с2 -1/н г / Чч _ V > „20^2 ІЦ I § (т))
2 т 2т2(с1+2)! Р { ^ 2{ })
1 а+2 (ег + 2)2(с?+1)2 т!
2 т 2т2 (т-гі-2)!(гі+2)!
•р2С^+2-і(і _р $з(т))