Лекция Райгородского Андрея Михайловича "Классические и новые задачи комбинаторики и теории графов"

7 апреля в лицее состоялась лекция профессора многих московских ВУЗов, лауреата премии президента РФ А.М.Райгородского. На лекции присутствовали как ученики и учителя лицея, так и представители других школ и ВУЗов.

"Сегодня в моей лекции вы не раз услышите слово катарсис", - так начинается лекция. Для начала рассматривается классическая задача комбинаторики - числа Рамсея: R(s, t) - минимальное число людей, такое, что среди них обязательно есть либо s попарно знакомых, либо t попарно незнакомых. Приводится пример R(3,3) и доказывается его существование. Затем ученики с лёгкостью отвечают на вопрос, что R(1,1)=1, R(1, t) = R(t, 1)= t. И в итоге на дом уходит "издевательская" задача - найти R(3, t), как сказал Андрей Михайлович: "до следующей лекции".
Затем немного углубляемся в историю создания чисел Рамсея и доказательства их нижней и верхней оценки (то есть, примерного значения). Узнаем историю великого математика Эрдёша и его учеников. 
Интересный факт: математики часто придумывают задачу и ставят ей цену, например, 3000$ или 50$. На сегодняшний день есть задача, оценённая всего в 100$, но так и не решенная до сих пор. 
После классической задачи Рамсея рассматривается несколько современных задач -"передний край науки": двудольные числа Рамсея, которые описываются с помощью двудольных полных графов. 
И заканчивает лектор ноткой обещанного катарсиса: "Хроматическое число пространства - минимальное число цветов, такое, чтоб одноцветные точки не были на расстоянии единицы".

Видео с лекцией А.М.Райгородского можно скачать по ссылке.