Случайные графы

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