On the chromatic numbers of random graphs

Мой доклад посвящён хроматическим числам случайных подграфов из некоторой последовательности графов. Прежде всего, мы коснёмся ряда классических результатов о хроматических числах графов Эрдеша -Реньи, после чего перейдём к обсуждению некоторых новых задач. Так, например, мы рассмотрим последовательность графов $G(n,r,s)$, где $n\to\infty$, и $r = r(n)$, $s = s(n)$. Множество вершин $G(n,r,s)$ состоит изо всех $r$ -подмножеств множества $\{1, \dots, n\}$. Любые две вершины соединены ребром, если отвечающие им множества пересекаются в точности по $s$ элементам. Такие графы возникают в теории кодирования, теории Рамсея и комбинаторной геометрии. В докладе будет дано определение случайных подграфов $G_{p}(n,r,s)$ графа $G(n,r,s)$, где $p = p(n)\in [0,1]$ – вероятность независимого включения ребра из $G(n,r,s)$, и приведены недавние результаты о хроматических числах таких случайных графов.