|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Закон нуля или единицы первого порядка для равномерной модели случайного графа
М. Е. Жуковскийab, Н. М. Свешниковc a Лаборатория продвинутой комбинаторики и сетевых приложений, Московский физико-технический институт (национальный исследовательский университет), г. Долгопрудный, Московская обл.
b Московский центр фундаментальной и прикладной математики
c Физтех-школа прикладной математики и информатики, Московский физико-технический институт (национальный исследовательский университет), г. Долгопрудный, Московская обл.
Аннотация:
Рассматривается случайный граф Эрдёша–Реньи в равномерной модели $G(n,m)$, где $m=m(n)$ – такая последовательность целых неотрицательных чисел, что $m(n)\sim cn^{\alpha}<(2-\varepsilon)n^2$ для некоторых $c>0$, $\alpha\in[0,2]$ и $\varepsilon>0$. Доказано, что $G(n,m)$ подчиняется закону нуля или единицы для языка первого порядка тогда и только тогда, когда либо $\alpha\in\{0,2\}$, либо $\alpha$ иррационально, либо $\alpha\in(0,1)$ и $\alpha$ не принадлежит множеству чисел вида $1-1/\ell$, $\ell\in\mathbb{N}$.
Библиография: 15 названий.
Ключевые слова:
закон нуля или единицы, логика первого порядка, равномерная модель случайного графа.
Поступила в редакцию: 21.08.2019 и 28.01.2020
Образец цитирования:
М. Е. Жуковский, Н. М. Свешников, “Закон нуля или единицы первого порядка для равномерной модели случайного графа”, Матем. сб., 211:7 (2020), 60–71; M. E. Zhukovskii, N. M. Sveshnikov, “First-order zero-one law for the uniform model of the random graph”, Sb. Math., 211:7 (2020), 956–966
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/sm9321https://doi.org/10.4213/sm9321 https://www.mathnet.ru/rus/sm/v211/i7/p60
|
Статистика просмотров: |
Страница аннотации: | 333 | PDF русской версии: | 59 | PDF английской версии: | 31 | Список литературы: | 33 | Первая страница: | 17 |
|