|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
Когда не выполнен $k$-закон нуля или единицы?
М. Е. Жуковскийa, А. Е. Медведеваb a Московский физико-технический институт (государственный университет), г. Долгопрудный Московской обл.
b Тамбовский государственный университет им. Г. Р. Державина
Аннотация:
В данной работе изучаются предельные вероятности
свойств первого порядка случайного графа
в модели Эрдеша–Реньи $G(n,n^{-\alpha})$, где $\alpha\in(0,1)$.
Говорят, что случайный граф $G(n,n^{-\alpha})$ подчиняется
$k$-закону нуля или единицы, если для любого свойства,
выражаемого формулой с кванторной глубиной, не превосходящей $k$,
вероятность этого свойства стремится либо к 0, либо к 1. Известно,
что при $\alpha=1-1/(2^{k-1}+a/b)$, где $a>2^{k-1}$,
выполнен $k$-закон нуля или единицы. Более того, закон нарушается
при $b=1$, $a \leqslant 2^{k-1}-2$. В данной работе мы доказали,
что $k$-закон не выполнен также при $b>1$,
$a \leqslant 2^{k-1}-(b+1)^2$.
Библиография: 11 названий.
Поступило: 08.07.2015 Исправленный вариант: 16.10.2015
Образец цитирования:
М. Е. Жуковский, А. Е. Медведева, “Когда не выполнен $k$-закон нуля или единицы?”, Матем. заметки, 99:3 (2016), 342–349; Math. Notes, 99:3 (2016), 362–367
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mzm10853https://doi.org/10.4213/mzm10853 https://www.mathnet.ru/rus/mzm/v99/i3/p342
|
Статистика просмотров: |
Страница аннотации: | 554 | PDF полного текста: | 76 | Список литературы: | 105 | Первая страница: | 67 |
|