• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

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

Мероприятие завершено

В этот четверг, 16 мая, в 14:40 состоится очередной семинар. С докладом выступит Андрей Купавский (МФТИ). 

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

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

16 мая 2024, аудитория G119
Для получения ссылки на семинар свяжитесь с Еленой Алямовской (ealyamovskaya@hse.ru или по тел: +7 911 772 61 23) с указанием вашего имени.