Пятница, 30 сентября, ауд. 106. Начало в 18:00.
Докладчик: Д.В. Карпов (ПОМИ РАН).
Тема: О правильных раскрасках гиперграфов.
Abstract
Пусть $\mathcal{H}$ --- гиперграф с максимальной степенью вершины $\Delta$, каждое гиперребро которого содержит не менее, чем $\delta$ вершин. Осенью 2010 года на семинаре рассказывалась теорема о том, что вершины $\mathcal{H}$ можно правильным образом покрасить в $\lceil \frac{2\Delta}{\delta} \rceil + 1 $ цветов (то есть так, чтобы в каждом гиперребре было хотя бы две разноцветных вершины). В этот раз будет рассказано новое, более простое доказательство этого факта.
Доклад по совместной работе с Н.В. Гравиным.