Дополнительные главы теории случайных графов

Случайные графы являются одной из наиболее динамично развивающихся в настоящее время математических дисциплин. Связано это с обширностей приложений этой дисциплины как в других математических задачах, так и на практике. Данный курс является продолжением курса «Случайные графы». В этот раз мы подробнее поговорим о связи равномерной и биномиальной моделей случайного графа, о пороговых вероятностях и о других важнейших свойствах случайного графа.

Для бесплатного просмотра доступны только часть материалов. Тесты на проверку откроются после оплаты сертификации. Стоимость сертификации составляет 3600 рублей.

1.    Монотонные свойства
Две модели случайных множеств и случайных графов. Случайные процессы на графах. Монотонные свойства и пороговые вероятности. Асимптотческая эквивалентность двух моделей. Пороговая вероятность для свойства содержать фиксированный подграф.
2.    Логические законы
Логика первого порядка. Законы нуля или единицы. Игра Эренфойхта. Свойства расширений. Законы нуля или единицы для плотного графа. Законы нуля или единицы для сильно разреженного графа. Законы нуля или единицы для разреженного графа.
3.    Эволюция случайного графа
p=o(1/n): ацикличность случайного графа и размер копмпонент; p=c/n: возникновения гигантской компоненты; пороговая вероятность связности
 

В результате обучения студент должен:
знать:
- определения двух моделей случайного графа и их взаимосвязи;
- асимптотическое поведение вероятностей свойств случайного графа, выразимых на языке первого порядка;
- динамику свойств случайного графа при росте p;
уметь:
- применять изученные методы для решения задач, связанных с различными моделями случайных графов;
- доказывать все изученные в курсе теоремы.