Geodesic
On the maximal cut in a random hypergraph
Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ, Tome 501 (2021), pp. 26-30

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DANMA_2021_501_a4,
     author = {P. A. Zakharov and D. A. Shabanov},
     title = {On the maximal cut in a random hypergraph},
     journal = {Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleni\^a},
     pages = {26--30},
     publisher = {mathdoc},
     volume = {501},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DANMA_2021_501_a4/}
}
TY  - JOUR
AU  - P. A. Zakharov
AU  - D. A. Shabanov
TI  - On the maximal cut in a random hypergraph
JO  - Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ
PY  - 2021
SP  - 26
EP  - 30
VL  - 501
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DANMA_2021_501_a4/
LA  - ru
ID  - DANMA_2021_501_a4
ER  - 
%0 Journal Article
%A P. A. Zakharov
%A D. A. Shabanov
%T On the maximal cut in a random hypergraph
%J Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ
%D 2021
%P 26-30
%V 501
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DANMA_2021_501_a4/
%G ru
%F DANMA_2021_501_a4
P. A. Zakharov; D. A. Shabanov. On the maximal cut in a random hypergraph. Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ, Tome 501 (2021), pp. 26-30. http://geodesic.mathdoc.fr/item/DANMA_2021_501_a4/