?
О максимальном разрезе в случайном гиперграфе
Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика). 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 is cn for some fixed c>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)$. Moreover, we obtain some bounds for the value of $\gamma(c, k, q)$.
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
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
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
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., Успехи математических наук 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., Дискретная математика 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
A. E. Khuzieva, Journal of Mathematical Sciences 2022 Vol. 262 No. 4 P. 581-590
We give probabilistic constructions of hypergraphs with large girth that do not admit panchromatic colorings. We prove new upper bounds on the minimal values of the number of edges and the maximum vertex degree in such hypergraphs. ...
Added: April 9, 2023
Демидович Ю. А., 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
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
Семенов А. С., Shabanov D. A., Проблемы передачи информации 2022 Т. 58 № 1 С. 80-111
We study the threshold probability for the property of existence of a special-form r-coloring for a random k-uniform hypergraph in the H(n, k, p) binomial model. A parametric set of j-chromatic numbers of a random hypergraph is considered. A coloring of hypergraph vertices is said to be j-proper if every edge in it contains no ...
Added: April 20, 2022
Sukhov A., Lyadova L. N., Порязов С. А., В кн. : Математика программных систем: межвуз. сб. науч. тр. Вып. 15.: Пермь : Пермский государственный национальный исследовательский университет, 2018. С. 97-104.
Different ways of the visual model descriptions formalization are considered. The hypergraph with poles is offered as a new formal model for graphic languages creation. This model provides possibility of definition and implementation of new visual languages and it gives a basis for realization of operations over the models constructed with these languages. The suggested ...
Added: January 18, 2019
Vasilyeva E., Romance M., Ivan Samoylenko et al., Entropy 2023 Vol. 25 No. 6 Article 923
We explore the metric structure of networks with higher-order interactions and introduce a novel definition of distance for hypergraphs that extends the classic methods reported in the literature. The new metric incorporates two critical factors: (1) the inter-node distance within each hyperedge, and (2) the distance between hyperedges in the network. As such, it involves ...
Added: July 28, 2023
Posypkin M., Усов А. Л., International Journal of Open Information Technologies 2016 Т. 4 № 8 С. 43-49
In this paper, we consider a method of storage, analysis and visualizing of large trees with the amount of 100 million nodes and more resulting in solving optimization problems by branch and bound algorithm. The solution provides a method for the collection of primary data from solver, analysis and processing of this data, as well ...
Added: October 6, 2016
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
Semchankau A., Shabanov D. A., Shkredov I., European Journal of Combinatorics 2022 Vol. 100 Article 103453
The paper deals with a problem of Additive Combinatorics. Let G be a finite abelian group of order n. We investigate the number of subset triples (A,B,C) such that for any x from A, y from B, c from C x+y is not equal to z. We prove the tight estimate for this value. As ...
Added: October 26, 2021
Switzerland : Springer, 2021
This book constitutes the refereed proceedings of the 12th International Conference on Optimization and Applications, OPTIMA 2021, held in Petrovac, Montenegro, in September-October 2021.
The 22 full and 3 short papers presented were carefully reviewed and selected from 63 submissions. The papers are organized into the following topical sub-headings: mathematical programming, global optimization, discrete and combinatorial ...
Added: November 4, 2021
Springer, 2022
The 21 full papers presented together with 6 invited abstracts lectures and 2 tutorial abstracts in this volume were carefully reviewed and selected from 88 submissions. The conference focuses on the following topics: Mathematical programming, bi-level and global optimization, integer programming and combinatorial optimization, approximation algorithms with theoretical guarantees and approximation schemes, heuristics and meta-heuristics, ...
Added: July 7, 2022
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
Springer, 2018
This book constitutes extended, revised and selected papers from the 7th International Conference on Optimization Problems and Their Applications, OPTA 2018, held in Omsk, Russia in July 2018. The 27 papers presented in this volume were carefully reviewed and selected from a total of 73 submissions. The papers are listed in thematic sections, namely location problems, ...
Added: June 25, 2018
Shabanov D. A., Доклады Академии наук 2017 Т. 475 № 1 С. 24-28
В работе исследуется проблема нахождения предельного распределения хроматического числа случайного однородного гиперграфа в разреженном случае. Показано, что для большей части значений параметров модели предельное значение хроматического числа концентрируется ровно в одной точке, которая может быть явно вычислена. ...
Added: July 19, 2017
Akhmejanova M., Balogh J., Dmitrii Shabanov, Discrete Applied Mathematics 2022 Vol. 321 P. 72-81
We deal with an extremal problem concerning panchromatic colorings of hypergraphs. A vertex r-coloring of a hypergraph is panchromatic if every edge meets every color. We prove a new bound for the edges that guarantees the existence of a panchromatic coloring with r colors. ...
Added: March 20, 2023
Shabanov D. A., Семенов А. С., Дискретная математика 2016 Т. 28 № 3 С. 126-144
Изучается асимптотическое поведение числа независимости для биномиальной модели случайного k-однородного гиперграфа H(n, k, p) в разреженном случае, когда p = c (n-k)!(k-1)!/(n−1)! при положительном постоянном c > 0. Показано, что существует такая константа γ(c) > 0, что число независимости α(H(n, k, p)) подчиняется закону больших чисел α(H(n, k, p))/n → γ(c) при n → +∞. ...
Added: December 27, 2016
Shabanov D. A., Шайхеева Т. М., Математические заметки 2020 Т. 107 № 3 С. 454-465
This paper deals with list colorings of uniform hypergraphs. Let H(m, r, k) be the complete r-partite k-uniform hypergraph with parts of equal size m in which each edge contains exactly one vertex from some k ≤ r parts. Using results on multiple covers by independent sets, we establish that, for fixed k and r, ...
Added: June 14, 2020
Shabanov D. A., Семенов А. С., Проблемы передачи информации 2018 Т. 54 № 1 С. 63-77
Изучается асимптотическое поведение числа j-независимости случайного k-однородного гиперграфа H(n,k,p) в биномиальной модели. Доказано, что в сильно разреженном случае, т.е. когда p=c/(n−1k−1) при положительном постоянном 0<c≤1/(k−1), существует такая константа γ(k,j,c)>0, что число j-независимости αj(H(n,k,p)) подчиняется закону больших чисел
αj(H(n,k,p))n−→Pγ(k,j,c) при n→+∞.
Более того, величина γ(k,j,c) предъявлена явно как функция от решения некоторого трансцендентного уравнения. ...
Added: September 3, 2018