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/

[1] Bayati M., Gamarnik D., Tetali P., “Combinatorial approach to the interpolation method and scaling limits in sparse random graphs”, The Annals of Probability, 41 (2013), 4080–4115 | DOI | MR | Zbl

[2] Daudé H., Martinez C., Rasendrahasina V., Ravelomanana V., “The max-cut of sparse random graphs”, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2012, 265–271 | DOI | MR | Zbl

[3] Bertoni A., Campadelli P., Posenato R., “An Upper Bound for the Maximum Cut Mean Value”, Lecture Notes in Computer Science, 1335, 1997, 78–84 | DOI | MR | Zbl

[4] Coppersmith D., Gamarnik D., Hajiaghayi M., Sorkin G., “Random maxsat, random maxcut, and their phase transitions”, Random Structures and Algorithms, 24 (2004), 502–545 | DOI | MR | Zbl

[5] Gamarnik D., Li Q., “On the max-cut over sparse random graph”, Random Structures and Algorithms, 52 (2018), 219–262 | DOI | MR | Zbl

[6] Dembo A., Montanari A., Sen S., “Extremal cuts of sparse random graphs”, The Annals of Probability, 45 (2017), 1190–1217 | DOI | MR | Zbl

[7] Coja-Oghlan A., Moore C., Sanwalani V., “Max k-cut and approximating the chromatic number of random graphs”, Random Structures and Algorithms, 28 (2006), 289–322 | DOI | MR | Zbl

[8] Kravtsov D.A., Krokhmal N.E., Shabanov D.A., “Panchromatic 3-colorings of random hypergraphs”, European Journal of Combinatorics, 78 (2019), 28–43 | DOI | MR

[9] Ayre P., Coja-Oghlan A., Greenhill C., “Hypergraph coloring up to condensation”, Random Structures and Algorithms, 54:4 (2019), 615–652 | DOI | MR | Zbl

[10] Ayre P., Greenhill C., “Rigid colorings of hypergraphs and contiguity”, SIAM Journal on Discrete Mathematics, 33 (2019), 1575–1606 | DOI | MR | Zbl

[11] Semenov A.S., “Dvukhtsvetnye raskraski sluchainogo gipergrafa”, Teoriya veroyatnostei i ee primeneniya, 64:1 (2019), 75–97 | DOI | MR | Zbl

[12] Semenov A., Shabanov D., “On the weak chromatic number of random hypergraphs”, Discrete Applied Mathematics, 276 (2020), 134–154 | DOI | MR | Zbl

[13] Shabanov D.A., “Estimating the r-colorability threshold for a random hypergraph”, Discrete Applied Mathematics, 282 (2020), 168–183 | DOI | MR | Zbl

[14] Balobanov A. E., Shabanov D. A., “On the strong chromatic number of a random 3-uniform hypergraph”, Discrete Mathematics, 344:3 (2021), 1–16 | DOI | MR

[15] Janson S., Łuczak T., Ruciński A., Random Graphs, Wiley, New York, 2000, 335 pp. | MR | Zbl