Андрей Михайлович Райгородский

Раскраски графов и их случайных подграфов

А. М. Райгородский планирует провести 3 занятия.

На первом занятии я расскажу про классическую задачу раскраски графа и объясню, как устроена «типичная» раскраска случайного графа.

На втором занятии я расскажу о некоторых дистанционных графах и их раскрасках. В частности, речь пойдет о замечательной теореме Эрдеша–Ко–Радо в экстремальной комбинаторике, которая крайне проста по формулировке и доказательство которой — это по сути олимпиадный трюк.

Наконец, третье занятие я посвящу случайным подграфам дистанционных графов, и мы обсудим свойство удивительной устойчивости результата Эрдеша–Ко–Радо относительно случайного уничтожения ребер дистанционного графа.

Думаю, что занятия будут доступны всем — и школьникам, и студентам. Все необходимые понятия я введу по ходу дела.

Organization Committee e-mail:
dubna@mccme.ru