?
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(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
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).
Publication based on the results of:
In book
Vol. 14. , Cham : Birkhäuser, 2021
Демидович Ю. А., Shabanov D. A., Теория вероятностей и ее применения 2022 Т. 67 № 2 С. 223-246
Работа посвящена изучению предельной концентрации значений хроматического числа случайного гиперграфа в биномиальной модели H(n,k,p). Доказано, что при фиксированном k>2 и не слишком быстро растущем значении n^{k-1}p хроматическое число H(n,k,p) с вероятностью, стремящейся к 1, принадлежит множеству из некоторых двух соседних значений. Кроме того, показано, что при чуть более сильных ограничениях на рост n^{k-1}p данные значения ...
Added: January 11, 2023
Shabanov D. A., Semenov A., Discrete Applied Mathematics 2020 Vol. 276 P. 134-154
The paper deals with weak chromatic numbers of random hypergraphs. Recall that a vertex coloring is said to be j-proper for a hypergraph if every j+1 vertices of any edge do not share a common color. The j-chromatic number of a hypergraph is the minimum number of colors required for a -proper coloring. We study ...
Added: October 31, 2019
Shabanov D. A., Kozik J., Duraj L., European Journal of Combinatorics 2021 Vol. 91 P. 1-11
In 1964 Erdos proved that $(1+\oh{1})) \frac{\eul \ln(2)}{4} k^2 2^{k}$ edges are sufficient to build a $k$-graph which is not two colorable. To this day, it is not known whether there exist such $k$-graphs with smaller number of edges.
Erd\H{o}s' bound is consequence of the fact that a hypergraph with $k^2/2$ vertices and $M(k)=(1+\oh{1}) \frac{\eul \ln(2)}{4} ...
Added: October 28, 2020
Popova S., Discrete Applied Mathematics 2024 Vol. 345 P. 215-225
The notion of spectrum for first-order properties introduced by J. Spencer for Erdős–Rényi random graph is considered in relation to random uniform hypergraphs. In this work we study the set of limit points of the spectrum for first-order formulae with bounded quantifier depth and obtain bounds for its maximum value. Moreover, we prove zero–one k-laws for ...
Added: February 3, 2024
Alina Khuzieva, Matveeva T., Dmitry Shabanov, Moscow Journal of Combinatorics and Number Theory 2023 Vol. 12 No. 1 P. 57-88
The paper deals with strong r-colorings of a random k-uniform hypergraph in the binomial model H(n,k,p). A vertex coloring is said to be strong for a hypergraph if any two vertices that share a common edge are colored with distinct colors. We consider the sparse case when the expected number of edges is equal to cn and the values r≥k≥3, c>0 remain constant ...
Added: April 10, 2023
Zakharov P., Shabanov D. A., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2021 Т. 501 С. 26-30
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 the expected number of edges ...
Added: April 20, 2022
Tiapkin D., Shabanov D. A., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2023 Т. 512 № 1 С. 52-57
The paper deals with the structure of the set of panchromatic colorings with three colors of a random hypergraph in the uniform model $H(n,k,m)$. It is well known that the property of the existence of a panchromatic coloring with given number of colors $r$ has the sharp threshold, i.e. there exists the threshold value $\widehat{m}_r=\widehat{m}_r(n)$ ...
Added: November 30, 2023
Popova S., Discrete Applied Mathematics 2021 Vol. 293 P. 134-142
The notion of spectrum for first-order properties introduced by J. Spencer for Erdős–Rényi random graph is considered in relation to random uniform hypergraphs. In this work we study the set of limit points of the spectrum for first-order formulae with bounded quantifier depth and give bounds for its minimum value. ...
Added: March 12, 2021
Balobanov A., Shabanov D. A., Discrete Mathematics 2021 Vol. 344 No. 3 Article 112231
This paper deals with estimating the threshold for the strong -colorability of a random 3-uniform hypergraph in the binomial model H(n,3,p). A vertex coloring is said to be strong for a hypergraph if every two vertices sharing a common edge are colored with distinct colors. It is known that the threshold corresponds to the sparse ...
Added: November 27, 2020
Demidovich Y., Shabanov D. A., , in : Recent Developments in Stochastic Methods and Applications: ICSM-5, Moscow, Russia, November 23–27, 2020, Selected Contributions. Vol. 371.: Springer, 2021. P. 190-203.
Added: September 23, 2021
Денисов И. О., Shabanov D. A., Дискретная математика 2021 Т. 33 № 4 С. 32-46
The paper deals with asymptotic behavior of the general independence numbers of random hypergraphs in the binomial model. We prove that there is a concentration of the values of the independence numbers in two consecutive numbers under the certain conditions on the parameters. ...
Added: April 20, 2022
T.A. Alexeeva, St. Petersburg Polytechnical University Journal: Physics and Mathematics 2015 Vol. 1 No. 2 P. 178-180
This paper presents a procedure for simulating random road disturbances based on the method of non-canonically decomposing random functions in the form of deterministic functions depending on just three random quantities under any probability distribution law. The mathematical methods developed for modeling random road disturbances give an accurate representation of the random function perturbations in ...
Added: February 23, 2016
Zakharov P., Shabanov D. A., Успехи математических наук 2023 Т. 78 № 6 (474) С. 183-184
We obtain very accurate estimates for the threshold probability of fractional (4:2)-colorability property in a random k-uniform hypergraph in the binomial model H(n,k,p). ...
Added: November 30, 2023
Shabanov D. A., Discrete Applied Mathematics 2020 Vol. 282 P. 168-183
The paper deals with estimating the r-colorability threshold for a random k-uniform hypergraph in the binomial model H(n,k,p). We consider the sparse case, when the expected number of edges is a linear function of n and prove a new lower bound for the sharp threshold of the property that H(n,k,p) is r-colorable. ...
Added: June 6, 2020
Popova S., Problems of Information Transmission 2018 Vol. 54 No. 3 P. 281-289
We study the asymptotic behavior of probabilities of first-order properties for random uniform hypergraphs. In 1990, J. Spencer introduced the notion of a spectrum for graph properties and proved the existence of a first-order property with an infinite spectrum. In this paper we give a definition of a spectrum for properties of uniform hypergraphs and ...
Added: October 4, 2019