Читать онлайн «Модели случайных графов»

Летняя школа «Современная математика» Дубна, июль  А. М. Райгородский Модели случайных графов Москва Издательство МЦНМО  УДК . .  ББК .  Р Р Райгородский А. М. Модели случайных графов. –– М. : МЦНМО, . ––  с. ISBN ---- Книга посвящена теории случайных графов. Эта теория находится на стыке комбинаторики, теории графов и теории вероятностей. Книга основана на лекциях, которые автор читал на школах «Со- временная математика» в Дубне и «Комбинаторная математика и тео- рия алгоритмов» в Судиславле, а также в Школе Анализа Данных Ян- декса. Книга предназначена для широкого круга читателей. ББК .  © Райгородский А. М. , . ISBN ---- © МЦНМО, . Оглавление Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  Глава  Некоторые основы теории вероятностей . . . . . . . . . . . . . . . .  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. 1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  2. 2. Определение модели Эрдёша –– Реньи . . . . . . . . . . . . . . .  2. 3. Одна естественная модификация модели . . . . . . . . . . . .  2. 4. Треугольники в случайных графах . . . . . . . . . . . . . . . . .  2. 4. 1.