Семинар HDI Lab: Концентрационные неравенства для нахождения разноцветных паросочетаний

Концентрационные неравенства для нахождения разноцветных паросочетаний

Рассмотрим k-дольный k-равномерный гиперграф на  [n]^k. Несложно видеть, что любой такой гиперграф с более чем  (s-1)n^{k-1} рёбрами содержит паросочетание размера s. Аарони и Бергер предложили рассмотреть разноцветный аналог этого вопроса: пусть даны  s гиперграфов, у каждого из которых больше, чем (s-1)n^{k-1} рёбер. Можем ли мы гарантировать существование паросочетания, в которым i-е ребро приходит из i-го гиперграфа? В этом докладе я расскажу практически полное решение этой задачи, основанное на некотором концентрационном неравенстве о пересечении семейства и случайного паросочетания. Совместная работа с Сергеем Киселёвым.