?
Полноцветные раскраски случайных гиперграфов
Дискретная математика. 2019. Т. 31. № 2. С. 84-113.
Publication based on the results of:
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
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
Gorsky A., Valba O. V., Journal of Complex Networks 2020 Vol. 8 No. 1 P. cnaa008
In this article, we show numerically the strong finite-size effects in exponential random graphs. Particularly, for the two-star model above the critical value of the chemical potential for triplets a ground state is a star-like graph with the finite set of hubs at network density p<0.5p<0.5 or as the single cluster at p>0.5p>0.5. We find that there exists ...
Added: August 28, 2020
Shabanov D. A., Хузиева А. Э., Математические заметки 2015 Т. 98 № 6 С. 948-951
Работа посвящена изучению известной проблемы экстремальной комбинаторики, связанной с раскрасками гиперграфов. исследуется минимальное число ребер в n-однородном гиперграфе с обхватом более s и хроматическим числом более r. Обоснована новая нижняя оценка данной величины. ...
Added: September 4, 2016
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., Kupavskii A., Combinatorics Probability and Computing 2018 Vol. 27 No. 2 P. 245-273
This paper deals with a combinatorial problem concerning colourings of uniform hypergraphs
with large girth. We prove a new lower bound for the maximum edge degree for an n-uniform non-r-colourable simple hypergraph. As an application of our probabilistic technique we establish a lower bound for the classical
van der Waerden number W(n, r), the minimum natural N ...
Added: February 22, 2018
Shabanov D. A., Доклады Академии наук 2017 Т. 475 № 1 С. 24-28
В работе исследуется проблема нахождения предельного распределения хроматического числа случайного однородного гиперграфа в разреженном случае. Показано, что для большей части значений параметров модели предельное значение хроматического числа концентрируется ровно в одной точке, которая может быть явно вычислена. ...
Added: July 19, 2017
Shabanov D. A., Балобанов А. Е., Математические заметки 2018 Т. 103 № 1 С. 38-48
В работе исследуются экстремальные задачи о числе j-независимых множеств в однородных простых гиперграфах. Получены близкие к оптимальным результаты для максимального количества независимых множеств в классе простых регулярных гиперграфов, а также для минимального числа - в классе простых гиперграфов с заданной средней степенью вершины. ...
Added: February 13, 2018
Shabanov D. A., Хузиева А. Э., Дискретная математика 2015 Т. 27 № 2 С. 112-133
В работе исследуется экстремальная проблема комбинаторного анализа об отыскании минимально возможного количества ребер в $n$-однородном гиперграфе с хроматическим числом больше $r$ и обхватом больше $s$. Получена новая нижняя оценка подобной экстремальной величины, а также ряд смежных результатов. ...
Added: February 23, 2016
Lebedeva A., Фундаментальная и прикладная математика 2014 Т. 19 № 2 С. 125-149
This paper deals with an extremal problem concerning hypergraph colorings. Let k be an integer. The problem is to find the value m(k,n) equal to the minimum number of edges in an n-uniform hypergraph not admitting two-colorings of the vertex set such that every edge of the hypergraph contains at least k vertices of each ...
Added: July 19, 2015
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
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
Cherkashin Danila, Electronic Journal of Combinatorics 2018 Vol. 25 No. #P1.47 P. 1-9
Intersecting and cross-intersecting families usually appear in extremal combinatorics in the vein of the Erd˝os–Ko–Rado theorem [4]. On the other hand, P. Erd˝os and L. Lov´asz in the noted paper [6] posed problems on coloring intersecting families as a restriction of classical hypergraph coloring problems to a special class of hypergraphs. This note deals with ...
Added: August 6, 2018
Molchanov S., Panov V., Успехи математических наук 2020 Т. 75 № 6 С. 107-152
В 30-е и 40-е годы двадцатого века в работах двух математиков -- Карла Дикмана и Василия Леонидовича Гончарова -- занимавшихся совершенно разными задачами, возникло одно и тоже уравнение с запаздыванием. В то время как в статье Дикмана исследовалось предельное значение количества натуральных чисел без больших делителей, работа Гончарова посвящена анализу асимптотики длины максимального цикла в разложении ...
Added: October 27, 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
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
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
Levashov M., Кухаренко А. В., Вопросы защиты информации 2018 № 2 С. 66-71
Рассматривается статистическая модель одного этапа системы фрод-мониторинга транзакций в интернет-банкинге. Построен и рассчитан близкий к отношению правдоподобия критерий отсева мошеннических транзакций. Для выборочных распределений, полученных на выборке объема в 1 млн реальных транзакций, вычислены параметры эффективности этого критерия. ...
Added: June 14, 2018