RUS  ENG
Полная версия
ЖУРНАЛЫ // Математический сборник // Архив

Матем. сб., 2015, том 206, номер 4, страницы 13–34 (Mi sm8368)

Эта публикация цитируется в 13 статьях

О наибольшей критической точке в $k$-законе нуля или единицы

М. Е. Жуковский

Московский физико-технический институт (государственный университет), г. Долгопрудный Московской обл.

Аннотация: Для случайного графа $G(n,n^{-\alpha})$ получено наибольшее значение $\alpha<1$, при котором не выполнен $k$-закон нуля или единицы для свойств первого порядка. Ранее было известно, что $k$-закон выполнен при всех $\alpha>1-1/(2^{k}-2)$ кроме $1-1/(2^{k}-1)$, $1-1/2^{k}$. При $\alpha=1-1/(2^k-2)$ закон нарушается. В работе доказана справедливость закона при $\alpha\in\{1-1/(2^{k}-1),1-1/2^{k}\}$.
Библиография: 17 названий.

Ключевые слова: закон нуля или единицы, случайный граф, свойства первого порядка, игра Эренфойхта, ограниченная кванторная глубина.

УДК: 519.179.4

MSC: Primary 05C80, 60F20; Secondary 03C07

Поступила в редакцию: 29.03.2014 и 25.09.2014

DOI: 10.4213/sm8368


 Англоязычная версия: Sbornik: Mathematics, 2015, 206:4, 489–509

Реферативные базы данных:


© МИАН, 2024