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