О максимальном разрезе в случайном гиперграфе

Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика). 2021. Т. 501. С. 26–30.

Захаров П. А., Шабанов Д. А.

В статье исследуется задача о нахождении максимального разреза в случайных гиперграфах. Рассматривается классическая биномиальная модель случайного $k$-одно\-родного гиперграфа $H(n, k, p)$ на $n$ вершинах и вероятностью $p=p(n)$. Основные результаты обобщают ранее известные результаты для случая графов и показывают, что в разреженном случае, (когда $p = cn/ \binom{n}{k}$ при $c=c(k) > 0$, не зависящем от $n$) существует такая $\gamma(c, k, q)>0$, что отношение величины максимального разреза $H(n, k, p)$ к числу вершин сходится к ней по вероятности. Кроме того, получены некоторые оценки величины $\gamma(c, k, q)$.

Ключевые слова: задачи оптимизации, optimization problems, случайные гиперграфы, hypergraphs, гиперграфы, random hypergraphs, cut of a hypergraph, interpolation method, разрез гиперграфа, метод интерполяции