?
On the weak chromatic number of random hypergraphs
Discrete Applied Mathematics. 2020. Vol. 276. P. 134-154.
Shabanov D. A., Semenov A.
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 the j-chromatic number of a random hypergraph in the binomial model H(n,k,p) in the case j=k-2 and investigate, for fixed k, the threshold for the property that j-chromatic number of does not exceed r. This threshold corresponds to the sparse case and the main result gives the tight bounds for it.
Publication based on the results of:
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
Kravtsov D., Krokhmal N., Shabanov D. A., Russian Mathematical Surveys 2018 Vol. 73 No. 4 P. 731-733
The paper deals with the problem of finding the probability threshold for the
existence of a panchromatic colouring for a random hypergraph in the binomial
model. ...
Added: November 15, 2018
Shabanov D. A., European Journal of Combinatorics 2015 Vol. 43 P. 185-203
An equitable two-coloring of a hypergraph $H=(V,E)$ is a proper vertex two-coloring such that the cardinalities of color classes differ by at most one. In connection with the property B problem Radhakrishnan and Srinivasan proved that if $H$ is a $k$-uniform hypergraph with maximum vertex degree $\Delta(H)$ satisfying
$$
\Delta(H)\leqslant c\,\frac {2^{k-1}}{\sqrt{k\,\ln k}}
$$
for some absolute constant ...
Added: October 6, 2015
Shabanov D. A., Graphs and Combinatorics 2014 Vol. 30 No. 5 P. 1249-1260
The work deals with a generalization of Erdos-Lovasz problem concerning colorings of non-uniform hypergraphs. We establish a new sufficient condition for r-colorability of a non-unifrom hypergraph with large edge sizes and girth at leats 4 in terms of expectation of the number of monochromatic edges in a random coloring. ...
Added: December 15, 2015
Shabanov D. A., Akolzin I., Discrete Mathematics 2016 Vol. 339 No. 12 P. 3020-3031
The paper deals with the classical extremal problem concerning colorings of hypergraphs. The problem is to find the value m(n,r), equal to the minimum number of edges in a n-uniform hypergraph with chromatic number greater than r. We obtain new upper and lower bounds for m(n,r) in the case when the parameter r is very ...
Added: September 4, 2016
Shabanov D. A., Doklady Mathematics 2017 Vol. 96 No. 1 P. 321-325
The problem on the limit distribution of the chromatic number of a random uniform hypergraph in the sparse case is studied. It is shown that, for most parameters values, the limit distribution of the chromatic number is concentrated at precisely one point, which can be found explicitly. ...
Added: March 6, 2018
Shabanov D. A., Akhmejanova M., Discrete Mathematics 2020 Vol. 343 No. 4 P. 1-11
The paper deals with an extremal problem concerning colorings of hypergraphs with bounded edge degrees. Consider the family of b-simple hypergraphs, in which any two edges do not share more than b common vertices. We prove a new lower bound for the maximum edge degree in a n-uniform b-simple non-r-colorable hypergraph. We also establish some ...
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
Akhmejanova M., Shabanov D. A., Discrete Applied Mathematics 2020 Vol. 276 P. 2-12
The paper deals with an extremal problem concerning equitable colorings of uniform hypergraphs. Recall that a vertex coloring of a hypergraph is called proper if there are no monochromatic edges under this coloring. A hypergraph is said to be equitably r-colorable if there is a proper coloring with r colors such that the sizes of ...
Added: October 31, 2019
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
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., Kozik J., Journal of Combinatorial Theory. Series B 2016 Vol. 116 P. 312-332
The paper deals with extremal problems concerning colorings of hypergraphs. By using a random recoloring algorithm we show that any n-uniform simple (i.e. every two distinct edges share at most one vertex) hypergraph H with not large maximum edge degree is r-colorable. As an application of our proof technique we establish a new lower bound ...
Added: December 15, 2015
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
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
Kotelnikova M. V., Aistov A., Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Социальные науки 2019 Т. 55 № 3 С. 183-189
The article describes a method that allows to improve the content of disciplines of the mathematical cycle by dividing them into invariant (general) and variable parts. The invariants were identified for such disciplines as «Linear algebra», «Mathematical analysis», «Probability theory and mathematical statistics» delivered to Bachelors program students of economics at several universities. Based on ...
Added: January 28, 2020
Borzykh D., ЛЕНАНД, 2021
Книга представляет собой экспресс-курс по теории вероятностей в контексте начального курса эконометрики. В курсе в максимально доступной форме изложен тот минимум, который необходим для осознанного изучения начального курса эконометрики. Данная книга может не только помочь ликвидировать пробелы в знаниях по теории вероятностей, но и позволить в первом приближении выучить предмет «с нуля». При этом, благодаря доступности изложения и небольшому объему книги, ...
Added: February 20, 2021
В. Л. Попов, Математические заметки 2017 Т. 102 № 1 С. 72-80
Мы доказываем, что аффинно-треугольные подгруппы являются борелевскими подгруппами групп Кремоны. ...
Added: May 3, 2017
Красноярск : ИВМ СО РАН, 2013
Труды Пятой Международной конференции «Системный анализ и информационные технологии» САИТ-2013 (19–25 сентября 2013 г., г.Красноярск, Россия): ...
Added: November 18, 2013
Grines V., Gurevich E., Pochinka O., Russian Mathematical Surveys 2017 Vol. 71 No. 6 P. 1146-1148
In the paper a Palis problem on finding sufficient conditions on embedding of Morse-Smale diffeomorphisms in topological flow is discussed. ...
Added: May 17, 2017
Okounkov A., Aganagic M., Moscow Mathematical Journal 2017 Vol. 17 No. 4 P. 565-600
We associate an explicit equivalent descendent insertion to any relative insertion in quantum K-theory of Nakajima varieties.
This also serves as an explicit formula for off-shell Bethe eigenfunctions for general quantum loop algebras associated to quivers and gives the general integral solution to the corresponding quantum Knizhnik Zamolodchikov and dynamical q-difference equations. ...
Added: October 25, 2018
Danilov B.R., Moscow University Computational Mathematics and Cybernetics 2013 Vol. 37 No. 4 P. 180-188
The article investigates a model of delays in a network of functional elements (a gate network) in an arbitrary finite complete basis B, where basis elements delays are arbitrary positive real numbers that are specified for each input and each set of boolean variables supplied on the other inputs. Asymptotic bounds of the form τ ...
Added: December 2, 2019
Min Namkung, Younghun K., Scientific Reports 2018 Vol. 8 No. 1 P. 16915-1-16915-18
Sequential state discrimination is a strategy for quantum state discrimination of a sender’s quantum
states when N receivers are separately located. In this report, we propose optical designs that can
perform sequential state discrimination of two coherent states. For this purpose, we consider not
only binary phase-shifting-key (BPSK) signals but also general coherent states, with arbitrary prior
probabilities. Since ...
Added: November 16, 2020
Beklemishev L. D., Оноприенко А. А., Математический сборник 2015 Т. 206 № 9 С. 3-20
We formulate some term rewriting systems in which the number of computation steps is finite for each output, but this number cannot be bounded by a provably total computable function in Peano arithmetic PA. Thus, the termination of such systems is unprovable in PA. These systems are derived from an independent combinatorial result known as the Worm ...
Added: March 13, 2016