Александр Александрович Разборов
Экстремальная комбинаторика
А.А.Разборов планирует провести 2–3 занятия.
В олимпиадных задачах многие слушатели сталкивались с вопросами о том, насколько большими (или малыми) могут быть семейства конечных объектов, удовлетворяющих определённым ограничениям. Не всем, однако, известно, что систематическим изучением вопросов такого рода занимается целая наука, называемая экстремальной комбинаторикой, и что эта наука изобилует трудными и красивыми теоремами, а также открытыми задачами с простой и естественной формулировкой, не поддающихся решению в течении десятилетий.
В нашем курсе мы, на примере некоторых классических результатов, поговорим об общих методах решения дискретных экстремальных задач, включая (довольно неожиданно!) алгебраические и аналитические методы. Типичные поводы для такого разговора включают:
- 1.Теорема Мантеля-Турана: сколько рёбер может содержать граф, не имеющий ни одной клики на k вершинах?
- 2.Теорема Шпернера: каково наибольшее возможное число подмножеств в n-элементном множестве с тем свойством, что ни одно не содержит другое?
- 3.Теорема Эрдеша-Секереша: какой максимальной длины может быть последовательность различных вещественных чисел, не содержащая ни возрастающей ни убывающей подпоследовательности из k элементов?
Organization Committee e-mail:
dubna@mccme.ru