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

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





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








Большой семинар кафедры теории вероятностей МГУ
24 ноября 2010 г. 16:45, г. Москва, ГЗ МГУ, ауд. 16-24
 


Метод случайной раскраски гиперграфов в задачах экстремальной комбинаторики

Д. А. Шабанов

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

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

Аннотация: В докладе будет рассказано о задачах теории раскрасок гиперграфов, которые находятся на стыке экстремальной и вероятностной комбинаторики. Данные задачи тесно связаны с классическими проблемами теории Рамсея (например, со знаменитой теоремой Рамсея), экстремальной теории множеств (проблема Турана и задачи о покрытии) и комбинаторной теории чисел (теорема Ван дер Вардена об арифметических прогрессиях).
Как и во многих других проблемах, наилучшие результаты в подобных задачах получаются применением различных вероятностных техник. Более того, именно в ходе исследования вопроса о существовании правильных раскрасок гиперграфов Л. Ловасом была доказана знаменитая Локальная лемма —утверждение о положительности вероятности одновременного выполнения конечного набора событий в условиях «малого числа зависимостей». В дальнейшем эта чисто вероятностная лемма нашла применение во многих других задачах комбинаторики, теории чисел, теоретической информатики и теории алгоритмов.
В докладе мы подробно остановимся на методе случайной раскраски, который на сегодняшний день является одним из наиболее эффективных способов получения оценок различных экстремальных величин, возникающих в теории раскрасок гиперграфов.

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