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