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