Модели случайных графов, Райгородский А.М., 2011

Модели случайных графов, Райгородский А.М., 2011.

   Книга посвящена теории случайных графов. Эта теория находится на стыке комбинаторики, теории графов и теории вероятностей. Книга основана на лекциях, которые автор читал на школах «Современная математика» в Дубне и «Комбинаторная математика и теория алгоритмов» в Судиславле, а также в Школе Анализа Данных Яндекса.
Книга предназначена для широкого круга читателей.




Классическая вероятность.
Представим себе обычную игральную кость — кубик, сделанный из идеально однородного материала. Если мы бросим такую кость на стол, то произойдет ровно одно из шести событий: либо кость выпадет кверху той гранью, на которой нарисована одна точка, либо той, на которой точек две, и так далее. Поскольку кость идеально однородная, разумно считать, что указанные события равновероятны. При этом они попарно несовместны в том смысле, что никакие два из них не происходят одновременно. Наконец, как мы уже говорили, одно из этих событий непременно случится. Все перечисленные обстоятельства позволяют сказать, что с вероятностью 1/6 кость выпадет заданной стороной кверху.

В общем случае классическая вероятность устроена совершенно аналогично. Есть некоторый набор событий w1, ..., wn. Они попарно несовместны, одно из них обязательно реализуется, и они равновероятны. Такие события называют элементарными, и полагают вероятность каждого из них равной 1/n.

ОГЛАВЛЕНИЕ.
Предисловие.
Глава 1 Некоторые основы теории вероятностей.
1.1. Классическая вероятность.
1.2. Схема Бернулли.
1.3. Схема серий.
1.4. Общее конечное вероятностное пространство.
1.5. Условные вероятности и независимость событий.
1.6. Несколько слов о бесконечных вероятностных пространствах.
1.7. Случайные величины и их распределения.
1.8. Моменты распределений.
1.9. Формула обращения и предельные теоремы пуассоновского типа.
1.10. Нормальная аппроксимация.
1.11. Неравенства Чебышёва и Маркова.
1.12. Уточнение неравенства Чебышёва в случае схемы Бернулли.
1.13. Условные вероятности и математические ожидания относительно разбиений.
1.14. Понятие о мартингале.
1.15. Неравенство Азумы.
Глава 2 Модель Эрдёша–Реньи случайного графа.
2.1. Введение.
2.2. Определение модели Эрдёша –– Реньи.
2.3. Одна естественная модификация модели.
2.4. Треугольники в случайных графах.
2.4.1. Постановка задачи и формулировки результатов.
2.4.2. Доказательство теоремы 10.
2.4.3. Доказательство теоремы 12.
2.4.4. Доказательство теоремы 11.
2.5. Связность случайного графа.
2.5.1. Формулировки результатов и комментарии к ним.
2.5.2. Доказательство теоремы 14.
2.5.3. Вокруг теоремы 13.
2.5.4. Гигантская компонента.
2.6. Хроматическое число случайного графа.
2.6.1. Определения, формулировки и комментарии.
2.6.2. Мартингалы реберного и вершинного типов.
2.6.3. Доказательство теоремы 18: формулировка леммы 1 и вывод из нее.
2.6.4. Доказательство теоремы 18: доказательство леммы 1.
2.6.5. Нижняя оценка в теореме 17.
2.6.6. Верхняя оценка в теореме 17: план действий.
2.6.7. Верхняя оценка в теореме 17: идея доказательства.
2.6.8. Верхняя оценка в теореме 17: выбор параметров и оценка вероятности.
2.6.9. Верхняя оценка в теореме 17: доказательство леммы 2.
2.6.10. Комментарий к лемме 2.
2.6.11. Чем Yk лучше Xk, или почему не работает неравенство Чебышёва?.
2.6.12. О функции u в теореме 18.
2.7. О числе независимости и кликовом числе случайного графа.
2.8. Числа Рамсея.
2.9. Хроматическое число и обхват графа.
2.10. Законы нуля или единицы.
2.10.1. Язык первого порядка для графов.
2.10.2. Формулировки результатов.
2.10.3. Игра Эренфойхта.
2.10.4. Выигрышная стратегия для Консерватора.
2.11. Еще ряд сюжетов.
2.11.1. Деревья в случайных графах.
2.11.2. Еще несколько слов о хроматическом числе случайного графа.
2.11.3. Планарность случайного графа.
2.11.4. Степени вершин случайного графа.
2.11.5. Изоморфизм случайных графов.
Глава 3 Обобщенная модель Эрдёша–Реньи и случайные дистанционные графы.
3.1. Определение модели.
3.2. Случайные подграфы куба.
3.3. Случайные дистанционные графы.
3.4. Вспомогательные факты и свойства полного дистанционного графа.
3.4.1. Немного простой аналитики.
3.4.2. О числе независимости полного графа расстояний.
3.4.3. О кликовом числе полного графа расстояний.
3.4.4. О хроматическом числе полного графа расстояний.
3.4.5. О числе ребер в произвольном подмножестве множества вершин полного графа расстояний.
3.4.6. «Олимпиадный» комментарий к предыдущему пункту.
3.5. Хроматическое и кликовое числа дистанционного графа.
3.6. Хроматическое число случайного дистанционного графа.
3.7. Дистанционные числа Рамсея.
3.7.1. Постановка задачи.
3.7.2. Формулировки результатов.
3.7.3. Доказательство теоремы 35.
3.7.4. Доказательство теоремы 37.
3.8. О связности случайного дистанционного графа.
3.9. Законы нуля или единицы для случайного дистанционного графа.
Глава 4 Модели случайных веб-графов.
4.1. Наблюдения Барабаши–Альберт.
4.2. Модель Боллобаша–Риордана.
4.2.1. Динамическая модификация.
4.2.2. Статическая модификация, или LCD-модель.
4.2.3. Некоторые результаты.
4.2.4. Доказательство теоремы 44 при k=1.
4.3. Модель копирования.
Глава 5 Приложение.
Литература.

Купить .





Теги: учебник по математике :: математика :: Райгородский :: числа Рамсе