Экстремальная комбинаторика. Лекция 2

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

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