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