Видеотека: A. M. Raigorodskii, On the chromatic numbers of random graphs

ВИДЕОТЕКА


Конференция по теории чисел и приложениям в честь 80-летия А. А. Карацубы 27 мая 2017 г. 12:10, г. Москва, Московский Государственный университет им. М.В. Ломоносова, механико-математический факультет

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)$, и приведены недавние результаты о хроматических числах таких случайных графов. Язык доклада: английский