Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://www.mccme.ru/dubna/2012/courses/razborov.htm
Дата изменения: Mon Jun 25 17:05:55 2012 Дата индексирования: Mon Feb 4 12:13:24 2013 Кодировка: koi8-r |
На главную страницу ЛШСМ-2012 | К списку курсов ЛШСМ-2012 |
Александр Александрович РазборовЭкстремальная комбинаторикаА.А.Разборов планирует провести 2–3 занятия. |
|
В олимпиадных задачах многие слушатели сталкивались с вопросами о том, насколько большими (или малыми) могут быть семейства конечных объектов, удовлетворяющих определённым ограничениям. Не всем, однако, известно, что систематическим изучением вопросов такого рода занимается целая наука, называемая экстремальной комбинаторикой, и что эта наука изобилует трудными и красивыми теоремами, а также открытыми задачами с простой и естественной формулировкой, не поддающихся решению в течении десятилетий.
В нашем курсе мы, на примере некоторых классических результатов, поговорим об общих методах решения дискретных экстремальных задач, включая (довольно неожиданно!) алгебраические и аналитические методы. Типичные поводы для такого разговора включают:
- Теорема Мантеля-Турана: сколько рёбер может содержать граф, не имеющий ни одной клики на k вершинах?
- Теорема Шпернера: каково наибольшее возможное число подмножеств в n-элементном множестве с тем свойством, что ни одно не содержит другое?
- Теорема Эрдеша-Секереша: какой максимальной длины может быть последовательность различных вещественных чисел, не содержащая ни возрастающей ни убывающей подпоследовательности из k элементов?