Александр Александрович Разборов Экстремальная комбинаторика А.А.Разборов планирует провести 2–3 занятия.

В олимпиадных задачах многие слушатели сталкивались с вопросами о том, насколько большими (или малыми) могут быть семейства конечных объектов, удовлетворяющих определённым ограничениям. Не всем, однако, известно, что систематическим изучением вопросов такого рода занимается целая наука, называемая экстремальной комбинаторикой, и что эта наука изобилует трудными и красивыми теоремами, а также открытыми задачами с простой и естественной формулировкой, не поддающихся решению в течении десятилетий.

В нашем курсе мы, на примере некоторых классических результатов, поговорим об общих методах решения дискретных экстремальных задач, включая (довольно неожиданно!) алгебраические и аналитические методы. Типичные поводы для такого разговора включают:

1. Теорема Мантеля-Турана: сколько рёбер может содержать граф, не имеющий ни одной клики на k вершинах?
2. Теорема Шпернера: каково наибольшее возможное число подмножеств в n-элементном множестве с тем свойством, что ни одно не содержит другое?
3. Теорема Эрдеша-Секереша: какой максимальной длины может быть последовательность различных вещественных чисел, не содержащая ни возрастающей ни убывающей подпоследовательности из k элементов?