Home

Пятница, 10 сентября, 18:00, к. 106

Пятница, 10 сентября, ауд. 106. Начало в 18:00.

Докладчик: Н. Гравин (ПОМИ РАН).

Тема: Один небольшой факт из жизни гиперграфов.

Abstract

Про раскраски гиперграфов на сегодняшний день известно не так много фактов и почти все нетривиальные утверждения доказываются с помощью вероятностных методов. В докладе будет изложено комбинаторное доказательство следующего факта: пусть $ \mathcal{H} $ --- гиперграф с максимальной степенью вершины $ \Delta $, каждое гиперребро которого содержит не менее, чем $ \delta $ вершин, тогда вершины $ \mathcal{H} $ можно правильным образом покрасить в $ \lceil \frac{2\Delta}{\delta} + 1 \rceil $ цветов (то есть так, чтобы в каждом гиперребре было хотя бы две разноцветных вершины). В качестве следствия мы выведем результат о динамических раскрасках вершин графа.