On the Maximum Cut in Sparse Random Hypergraphs
The paper deals with the max-cut problem for random hypergraphs. We consider a binomial model of a random k-uniform hypergraph H(n, k, p) for some fixed k≥3k≥3, growing n and p=p(n)p=p(n). For given natural number q, the max-q-cut for a hypergraph is the maximal possible number of edges that can be properly colored with q colors under the same coloring. Generalizing the known results for graphs we show that in the sparse case (when p=cn/(nk)p=cn/(nk) for some fixed c>0c>0 not depending on n) there exists a limit constant γ(c,k,q)γ(c,k,q) such that
as n→+∞n→+∞. We also prove some estimates for γ(c,k,q)γ(c,k,q) of the form Ak,q⋅c+Bk,q⋅c√+o(c√)Ak,q⋅c+Bk,q⋅c+o(c).