Андрей Михайлович Райгородский

Модели случайных графов

А.М. Райгородский планирует провести 3 занятия.

Занятие 1. На этом занятии будет рассмотрена классическая модель Эрдеша–Реньи случайного графа. Будут изучены вопросы связности случайного графа в этой модели, а также задачи о распределении степеней его вершин.

Занятие 2. На этом занятии мы сперва скажем несколько слов о хроматическом числе случайного графа в модели Эрдеша–Реньи. Оказывается, "почти всякий" граф в этой модели имеет "большое" хроматическое число и в то же время не содержит "больших" полных подграфов. Затем мы обсудим аналогичные свойства так называемых графов расстояний, которые возникают в связи с классической проблемой о раскраске пространства. Для этого нам понадобится новая модель случайного графа.

Занятие 3. На последнем занятии мы поговорим об одном из самых современных направлений в теории случайных графов. А именно, мы изучим модель Боллобаша–Риордана случайного "веб-графа", позволяющую весьма адекватно описывать динамику роста интернета. Разумеется, эта модель будет очень сильно отличаться и от модели Эрдеша–Реньи, и от модели случайного графа расстояний. Удивительным образом, эта модель окажется связанной с комбинаторикой хордовых диаграмм.

Organization Committee e-mail:
dubna@mccme.ru