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

Семинар МЛ ТИ "Об оптимальных распределениях цветов в задаче о максимальном разрезе гиперграфа"

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

Дата: 22 октября 2026 г, 18:10 - 19:30

Аннотация: Рассматривается k-однородный гиперграф: каждое его ребро содержит ровно k вершин. При дробной (a:b)-раскраске каждой вершине назначается набор из b цветов, выбранных из a доступных. Ребро считается разрезанным, если у всех его вершин нет общего цвета.
Для максимального разреза случайного гиперграфа существуют двусторонние оценки, в которые входит максимальная вероятность разрезать ребро при независимом выборе наборов цветов по общему распределению. Доклад посвящён точному вычислению этой вероятности и описанию оптимальных распределений. Основной результат - полное решение случая b=2: для любого числа цветов a и любого размера ребра k найдены точное значение максимума и все распределения пар цветов, на которых он достигается.

Место проведения: Покровский бульвар,11, аудитория R407

Ссылка для подключения