Раскраски графов и их случайных подграфов. Лекция 1

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