?
О концентрации значений чисел независимости случайных гиперграфов
Дискретная математика. 2021. Т. 33. № 4. С. 32-46.
Денисов И. О., Шабанов Д. А.
В работе исследуется асимптотическое поведение общих чисел независимости случайных гиперграфов в биномиальной модели. Доказано, что в определенной области изменения параметров имеет место предельная концентрация числа независимости в двух соседних значениях.
Демидович Ю. А., Шабанов Д. А., Теория вероятностей и ее применения 2022 Т. 67 № 2 С. 223-246
Работа посвящена изучению предельной концентрации значений хроматического числа случайного гиперграфа в биномиальной модели H(n,k,p). Доказано, что при фиксированном k>2 и не слишком быстро растущем значении n^{k-1}p хроматическое число H(n,k,p) с вероятностью, стремящейся к 1, принадлежит множеству из некоторых двух соседних значений. Кроме того, показано, что при чуть более сильных ограничениях на рост n^{k-1}p данные значения ...
Добавлено: 11 января 2023 г.
Alina Khuzieva, Matveeva T., Dmitry Shabanov, Moscow Journal of Combinatorics and Number Theory 2023 Vol. 12 No. 1 P. 57-88
Добавлено: 10 апреля 2023 г.
Денисов И. О., Шабанов Д. А., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2023 Т. 509 № 1 С. 28-35
Работа посвящена изучению предельного поведения j-хроматических чисел случайного k-однородного гиперграфа в биномиальной модели H(n,k,p). Рассматривается разреженный случай, когда среднее число ребер является линейной функцией от числа вершин n, т.е. равно cn, где c>0 не зависит от n. Доказано, что при всех достаточно больших значениях c величина j-хроматического числа H(n,k,p) с вероятностью, стремящейся к 1, концентрируется в одном или ...
Добавлено: 25 октября 2023 г.
Матвеева Т. Г., Хузиева А. Э., Шабанов Д. А., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2022 Т. 502 С. 37-41
Работа посвящена изучению пороговой вероятности для свойства наличия сильной раскраски в заданное число цветов у случайного k-однородного гиперграфа в биномиальной модели H(n,k,p). Раскраска множества вершин гиперграфа называется сильной, если в ней в каждом ребре не найдется двух вершин одинакового цвета. Исследуется вопрос о нахождении точной пороговой вероятности наличия сильной раскраски в q цветов у H(n,k,p). ...
Добавлено: 11 января 2023 г.
Тяпкин Д. Н., Шабанов Д. А., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2023 Т. 512 № 1 С. 52-57
В работе исследуется структура множества полноцветных раскрасок в три цвета у случайного гиперграфа в равномерной модели $H(n,k,m)$. Хорошо известно, что свойство наличия полноцветной раскраски в заданное число цветов $r$ имеет точную пороговую функцию, такое пороговое значение $\widehat{m}_r=\widehat{m}_r(n)$, что для любого $\varepsilon>0$ при $m\leqslant (1-\varepsilon)\widehat{m}_r$ случайный гиперграф $H(n,k,m)$ с вероятностью, стремящейся к 1 при $n\to\infty$, обладает ...
Добавлено: 30 ноября 2023 г.
Захаров П. А., Шабанов Д. А., Успехи математических наук 2023 Т. 78 № 6 (474) С. 183-184
В работе получены весьма точные оценки пороговой вероятности для свойства дробной (4:2)-раскрашиваемости в случайном k-однородном гиперграфе в биномиальной модели H(n,k,p). ...
Добавлено: 30 ноября 2023 г.
Добавлено: 28 октября 2020 г.
Семенов А. С., Шабанов Д. А., Проблемы передачи информации 2022 Т. 58 № 1 С. 80-111
Работа посвящена изучению пороговой вероятности для свойства наличия раскраски в $r$ цветов специального вида у случайного $k$-однородного гиперграфа в биномиальной модели $H(n,k,p)$. Рассматривается параметрическое множество $j$-хроматических чисел случайного гиперграфа. Раскраска множества вершин гиперграфа называется $j$-правильной, если в ней каждое ребро содержит не более $j$ вершин каждого цвета. Исследуется вопрос о нахождении точной пороговой вероятности наличия ...
Добавлено: 20 апреля 2022 г.
Balobanov A., Шабанов Д. А., Discrete Mathematics 2021 Vol. 344 No. 3 Article 112231
Добавлено: 27 ноября 2020 г.
Захаров П. А., Шабанов Д. А., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2021 Т. 501 С. 26-30
В статье исследуется задача о нахождении максимального разреза в случайных гиперграфах. Рассматривается классическая биномиальная модель случайного $k$-одно\-родного гиперграфа $H(n, k, p)$ на $n$ вершинах и вероятностью $p=p(n)$. Основные результаты обобщают ранее известные результаты для случая графов и показывают, что в разреженном случае, (когда $p = cn/ \binom{n}{k}$ при $c=c(k) > 0$, не зависящем от $n$) ...
Добавлено: 20 апреля 2022 г.
Demidovich Y., Шабанов Д. А., , 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.
Добавлено: 23 сентября 2021 г.
Шабанов Д. А., Семенов А. С., Проблемы передачи информации 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) предъявлена явно как функция от решения некоторого трансцендентного уравнения. ...
Добавлено: 3 сентября 2018 г.
Шабанов Д. А., Семенов А. С., Дискретная математика 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 → +∞. ...
Добавлено: 27 декабря 2016 г.
Симарова Е. Н., Записки научных семинаров ПОМИ РАН 2017 Т. 464 С. 112-131
Доказано, что в связном графе минимальной степени хотя бы 6 существует остовное дерево, в котором более $\frac{11}{21}$ всех вершин -- листья. ...
Добавлено: 19 апреля 2021 г.
Шабанов Д. А., Доклады Академии наук 2017 Т. 475 № 1 С. 24-28
В работе исследуется проблема нахождения предельного распределения хроматического числа случайного однородного гиперграфа в разреженном случае. Показано, что для большей части значений параметров модели предельное значение хроматического числа концентрируется ровно в одной точке, которая может быть явно вычислена. ...
Добавлено: 19 июля 2017 г.
Добавлено: 4 февраля 2019 г.
Шабанов Д. А., Semenov A., Discrete Applied Mathematics 2020 Vol. 276 P. 134-154
Добавлено: 31 октября 2019 г.
Сиротин В. П., Архипова М. Ю., Дуброва Т. А. и др., Bielsko-Biala : University of Bielsko-Biala Press, 2016
Добавлено: 2 ноября 2016 г.
Пахомов Ф. Н., Известия РАН. Серия математическая 2016 Т. 80 № 6 С. 173-216
Полимодальная логика доказуемости
GLP была введена Г. К. Джапаридзе в 1986 г. Она является логикой доказуемости для ряда цепочек предикатов доказуемости возрастающей силы. Всякой полимодальной логике соответствует многообразие полимодальных алгебр. Л. Д. Беклемишевым и А. Виссером был поставлен вопрос о разрешимости элементарной теории свободной GLP-алгебры, порожденной константами 0, 1 [1]. В этой статье для любого натурального n решается аналогичный вопрос для логик GLPn, являющихся ...
Добавлено: 4 декабря 2017 г.
Фурманов К. К., Nikol'skii I. M., Computational Mathematics and Modeling 2016 Vol. 27 No. 2 P. 247-253
Добавлено: 22 декабря 2016 г.
Buchstaber V., Лимонченко И. Ю., / Cornell University. Series math "arxiv.org". 2018. No. 1808.08851.
Добавлено: 29 сентября 2019 г.