Home

Пятница 30 сентября, 18-00, ауд. 106

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

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

Тема: О правильных раскрасках гиперграфов.

Abstract

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