Abstract:
This paper deals with the problem of finding the max-cut for random hypergraphs. We consider the classical binomial model $H(n,k,p)$ of a random $k$-uniform hypergraph on $n$ vertices with probability $p=p(n)$. The main results generalize previously known facts for the graph case and show that in the sparse case (when $\displaystyle p=cn/\binom{n}{k}$ for some fixed $c=c(k)>0$ independent of $n)$ there exists $\gamma(c,k,q)>0$ such that the ratio of the maximal cut of $H(n,k,p)$ to the number of vertices converges in probability to $\gamma(c,k,q)>0$. Moreover, we obtain some bounds for the value of $\gamma(c,k,q)$.
Keywords:hypergraphs, random hypergraphs, cut of a hypergraph, interpolation method, optimization problem.
UDC:519.174
Presented:A. N. Shiryaev Received: 11.08.2021 Revised: 17.08.2021 Accepted: 08.09.2021