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

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





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








Петербургский семинар по теории представлений и динамическим системам
14 марта 2018 г. 17:00, г. Санкт-Петербург, ПОМИ, ауд. 311 (наб. р. Фонтанки, 27)
 


Экстремальные задачи в раскрасках гиперграфов

Д. Д. Черкашин

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

Аннотация: Гиперграф есть пара $(V, E)$, где $V$ — конечное множество вершин, $E\subset 2^V$ — семейство его подмножеств. Гиперграф называется $n$-однородным, если каждое его ребро имеет размер $n$.
Я расскажу о задаче Эрдёша–Хайнала, которая заключается в нахождении минимального (по количеству ребер) $n$-однородного гиперграфа с хроматическим числом 3 (то есть такого, что любая 2-раскраска вершин содержит одноцветное ребро), и её обобщениях. Наиболее общий вид задачи — поиск маленьких “нетривиальных” гиперграфов. Большинство результатов в этой области получается вероятностными методами.

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