Список тем для обсуждения на зачете.
- Классические модели случайных графов.
- Свойства случайных графов и их типы.
- Монотонность и выпуклость свойств графов и их следствия.
- Пороговые вероятности и их свойства.
- Применение случайных графов в задаче об обхвате графа и его хроматическом числе.
- Метод первого и второго моментов.
- Сбалансированные и строго сбалансированные графы.
- Свойство содержать заданный граф как подграф: основные результаты.
- Индуцированные подграфы и связь с обычными подграфами при p->0.
- Компоненты связности, изоморфные заданному подграфу.
- Связность случайных графов и связь с наличием изолированных вершин.
- Метод моментов для доказательства предельных теорем.
- Предельные теоремы для числа способов вложить заданный строго сбалансированный граф в случайный (пуассоновский и нормальный пределы).
- Предельные теоремы для числа способов вложить несбалансированный граф в случайный, примеры.
- Максимальный размер компонент связности случайного графа, фазовый переход.
- Ветвящиеся процессы и их свойства.
- Спаривание пуассоновского и биномиального ветвящихся процессов.
- Связь случайных графов и биномиального ветвящегося процесса.
- Размер максимальной компоненты связности в критическом режиме.
- Обобщенный случайный граф, определяемый по весам вершин.
Конфигурационная модель.
Литература:
1. B. Bollobas, Random graphs, Cambridge University Press, Cambridge, 2001.
2. S. Jansen, T. Luczak, A. Rucinski, Random graphs, Wiley-Interscience, New York, 2000.
3. R. van der Hofstad, Random Graphs and Complex Networks, Lecture notes.
4. В.Ф. Колчин. Случайные графы. М.: Физматлит, 2002.
5. А.М. Райгородский. Модели случайных графов. М.: МЦНМО, 2011.
Последние 2 книги на русском, но, к сожалению, не очень пересекаются с данными вопросами.