• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book chapter

On the Maximum Cut in Sparse Random Hypergraphs

P. 817-822.

The paper deals with the max-cut problem for random hypergraphs. We consider a binomial model of a random k-uniform hypergraph H(nkp) 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

max-q-cut(H(n,k,p))n⟶Pγ(c,k,q)max-q-cut(H(n,k,p))n⟶Pγ(c,k,q)

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).