Экстремальная теория графов

В МФТИ на первый курс поступает множество студентов, и они начинают знакомиться друг с другом: появляются всё новые и новые пары знакомых. В какой-то момент возникают тройки попарно знакомых людей, компании знакомых из четырёх человек и т.д. Можно задаться вопросом: а сколько пар студентов достаточно перезнакомить, так, чтобы гарантированно появилась тройка попарно знакомых? В терминах теории графов: сколько рёбер нужно провести в графе, чтобы в нём гарантированно возникла клика на трёх вершинах? Подобными вопросами о плотностях графов как раз и занимается в первую очередь экстремальная теория графов. Исторически первыми были результаты о предельных плотностях графов, при которых возникают клики (наборы вершин, попарно соединённых рёбрами), но столь же естественен, например, вопрос о том, какое число рёбер будет гарантировать наличие в графе, скажем, пути на заданном числе вершин. В зависимости от того, какой подграф нам нужен, задачи здесь сильно варьируются по сложности от школьных упражнений до нерешённых научных проблем.
Миклош Шимонович, сам внёсший большой вклад в развитие экстремальной теории графов, расскажет о современном состоянии этой науки, известных решённых и открытых задачах, методах получения результатов. В частности, речь пойдёт о недавнем решении знаменитой гипотезы Эрдёша—Шош о поддеревьях, полученном им в соавторстве с М. Айтаем, Я. Комлошем, Э. Семереди. Гипотеза Эрдёша—Шош оставалась неприступной полвека.
Лекция пройдет в 239 аудитории Нового корпуса МФТИ с 18:30 до 20:00 в среду 28-го октября. Двери МФТИ будут открыты для всех! С вопросами обращайтесь к А.М. Райгородскому: mraigor@yandex.ru