RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Межкафедральный семинар МФТИ по дискретной математике
28 октября 2015 г. 18:30–20:00, г. Долгопрудный, г. Долгопрудный, 239 аудитория Нового корпуса МФТИ
 


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

Миклош Шимонович

Alfréd Rényi Institute of Mathematics, Hungary Academy of Sciences

Количество просмотров:
Эта страница:60

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

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020