Пятница, 30 сентября, ауд. 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)
вершин. Осенью 2010 года на семинаре рассказывалась теорема о том, что вершины
![$ \mathcal{H} $](../../../sites/default/files/tex/d376da22e089250d0f16735e18392df730962205/index.png)
можно правильным образом покрасить в
![$ \lceil \frac{2\Delta}{\delta} \rceil + 1 $](../../../sites/default/files/tex/ce172667e2d15ba1b59d3d1e8215c4b7580a62ea/index.png)
цветов (то есть так, чтобы в каждом гиперребре было хотя бы две разноцветных вершины). В этот раз будет рассказано новое, более простое доказательство этого факта.
Доклад по совместной работе с Н.В. Гравиным.