[Коллоквиум]: Случайные графы

Спикер: Андрей Райгородский - Московский государственный университет имени М.В. Ломоносова В 1959 году П. Эрдеш и А. Реньи начали изучать биномиальную модель случайного графа G(n, p), в которой ребра графа на n вершинах возникают взаимно независимо с одной и той же вероятностью p. За прошедшие десятилетия наука о случайных графах Эрдеша-Реньи сделалась одной из центральных дисциплин в области комбинаторики и ее приложений. Одно из наиболее естественных обобщений модели Эрдеша-Реньи состоит в следующем: берется некоторая последовательность графов Hn, и в каждом из графов Hn ребра сохраняются взаимно независимо с одной и той же вероятностью p. Возникают случайные графы Hn, p. В последнее время очень много исследований посвящено именно такому варианту модели Эрдеша-Реньи. Мы расскажем об одной последовательности графов, важной для комбинаторной геометрии и теории кодирования. Для этой последовательности графов мы рассмотрим описанный выше вариант модели Эрдеша-Реньи и обсудим различные старые и новые результаты, которые здесь удалось получить. В частности, речь пойдет о раскрасках таких случайных графов, об их кликовых числах и их числах независимости.