Доклады Российской академии наук. Математика, информатика, процессы управления, 2021, T. 500, № 1, стр. 31-34

1. ЛОГИКА ПЕРВОГО ПОРЯДКА СЛУЧАЙНОГО ГРАФА

Простым графом (далее просто графом) $G$ называется пара множеств $G = (V,E)$, где V – произвольное непустое множество, а $E$ – некоторое множество неупорядоченных пар различных элементов из V. Под изоморфизмом графов ${{G}_{1}}$ = (V₁, E₁), ${{G}_{2}} = ({{V}_{2}},{{E}_{2}})$ подразумевается биекция $f:{{V}_{1}} \to {{V}_{2}}$, сохраняющая ребра, т.е. {x, y} ∈ ${{E}_{1}} \Leftrightarrow {\text{\{ }}f(x),f(y){\text{\} }}$ ∈ ∈ E₂.  Свойство графов – множество графов, замкнутое относительно изоморфизма. Для формализации некоторых свойств графов используется язык первого порядка. Так, например, свойство содержать треугольник (тройку вершин, попарно соединенных ребрами) записывается формулой первого порядка

Свойство графа иметь изолированную вершину (вершину, из которой не исходит ни одно ребро) записывается формулой первого порядка

Говоря простыми словами, формула первого порядка – это формальная запись свойства, использующая символы переменных ($x,{{x}_{1}},y,z, \ldots $), булевы связки ($ \wedge , \vee ,\neg , \Rightarrow , \Leftrightarrow $), предикатные символы (в случае графов =, ~), кванторы ($\forall ,\exists $) и скобки. Строгое определение формулы первого порядка можно найти, например, в [1]. Под сигнатурой формулы подразумевается множество предикатных символов $\mathcal{P}$ с заданными арностями (т.е. натуральными числами, обозначающими количество аргументов соответствующего предиката). Под интерпретацией подразумевается множество $\mathcal{D}$ и отображение $\sigma $, ставящее в соответствие каждому символу из $\mathcal{P}$ предикат ${{\mathcal{D}}^{a}} \to {\text{\{ }}0,1{\text{\} }}$, где a – арность этого предикатного символа. В случае графов сигнатура состоит из двух предикатных символов ~, =, а интерпретациями являются конечные простые графы (предикат $x \sim y$ является истинным для вершин x, y, соединенных ребром). Иными словами, для интерпретации $G$ на $n$ вершинах:

1) $\mathcal{D} = {\text{\{ }}1, \ldots ,n{\text{\} }}$ – множество вершин графа $G$,

2) предикат ~ истинен на вершинах x, y тогда и только тогда, когда x, y соединены ребром в $G$,

3) предикат $ = $ истинен на совпадающих вершинах x, y.

Логика первого порядка обладает рядом важных свойств, одним из которых является теорема Гёделя о полноте [1]. Из этой теоремы, в частности, следует так называемый закон 0 или 1. Для графов это утверждение звучит следующим образом. Пусть φ – формула первого порядка, а ${{G}_{n}}$ – множество графов на множестве вершин ${\text{\{ }}1, \ldots ,n{\text{\} }}$, для которых формула φ является истинной. Тогда

Заметим, что ${{2}^{{C_{n}^{2}}}}$ – это количество всех графов на ${\text{\{ }}1, \ldots ,n{\text{\} }}$. Закон 0 или 1 был впервые доказан Глебским, Коганом, Легоньким и Талановым в 1969 г. [2] и далее в 1976 г. он независимо (и по-другому) был доказан Фейгиным [3]. Чтобы заметить, что закон 0 или 1 вытекает из теоремы Гёделя, достаточно построить так называемую систему аксиом расширения и доказать, что ни для какого конечного графа не истинны все эти аксиомы одновременно, но существует единственный счетный граф $R$, для которого они истинны (этот граф называется графом Радо, и с вероятностью 1 он изоморфен случайному счетному графу в биномиальной модели) [4]. Действительно, упомянутая система аксиом является почти наверное теорией, т.е. любая аксиома истинна на почти всех графах, а значит, то же самое верно и для любой выводимой из нее формулы (т.е. формулы, истинной на всех графах, на которых истинен и некоторый конечный набор аксиом). По теореме Гёделя любая формула, истинная на $R$, истинна на почти всех графах. Наоборот, если формула φ не является истинной на $R$, то $\neg \varphi $ – истинна, а значит, истинна на почти всех графах. Единственным нетривиальным моментом в этом доказательстве является единственность графа Радо (существование счетного графа следует из непротиворечивости упомянутой системы аксиом, см. [1]).

Альтернативное доказательство [5] закона 0 или 1 опирается на теорему Эренфойхта [6], связывающую игру Эренфойхта с понятием элементарной эквивалентности. Напомним, что кванторной глубиной формулы q(φ) называется количество кванторов в самой длинной последовательности вложенных кванторов в этой формуле (см. формальное определение в [1]). Будем говорить, что графы ${{G}_{1}},{{G}_{2}}$ являются k-элементарно экивалентными, если для любой формулы первого порядка φ с ${\mathbf{q}}(\varphi ) = k$ либо φ истинна на ${{G}_{1}},{{G}_{2}}$, либо ложна на ${{G}_{1}},{{G}_{2}}$. В игре Эренфойхта на графах ${{G}_{1}},{{G}_{2}}$ с k раундами участвуют два игрока, Новатор и Консерватор. В $\nu $-м раунде ($1 \leqslant \nu \leqslant k$) Новатор выбирает вершину из любого графа, отличную от уже выбранных. Затем Консерватор выбирает вершину из другого графа, отличную от уже выбранных. К концу игры выбраны вершины ${{x}_{1}}, \ldots ,{{x}_{k}} \in V({{G}_{1}})$ и ${{y}_{1}}, \ldots ,{{y}_{k}} \in V({{G}_{2}})$. Консерватор побеждает в том и только том случае, когда отображение f: {x₁, ..., ${{x}_{k}}{\text{\} }} \to {\text{\{ }}{{y}_{1}}, \ldots ,{{y}_{k}}{\text{\} }}$, переводящее вершину ${{x}_{\nu }}$ в вершину ${{y}_{\nu }}$ для каждого $\nu \in {\text{\{ }}1, \ldots ,k{\text{\} }}$, является изоморфизмом индуцированных подграфов ${{G}_{1}}{{{\text{|}}}_{{{\text{\{ }}{{x}_{1}},...,{{x}_{k}}{\text{\} }}}}}$ и ${{G}_{2}}{{{\text{|}}}_{{{\text{\{ }}{{y}_{1}}, \ldots ,{{y}_{k}}{\text{\} }}}}}$. Теорема Эренфойхта утверждает, что графы ${{G}_{1}},{{G}_{2}}$ являются k-элементарно эквивалентными тогда и только тогда, когда у Консерватора есть выигрышная стратегия на ${{G}_{1}},{{G}_{2}}$ в k раундах.

Из теоремы Эренфойхта можно (см., например, [4, 7]) получить следствие о справедливости законов 0 или 1: закон 0 или 1 справедлив для любой формулы первого порядка φ с ${\mathbf{q}}(\varphi ) \leqslant k$ тогда и только тогда, когда у Консерватора есть выигрышная стратегия в k раундах на почти всех графах (иными словами,

где ${{\mathcal{G}}_{{n,m}}}$ – множество пар графов G₁ на ${\text{\{ }}1, \ldots ,n{\text{\} }}$ и ${{G}_{2}}$ на ${\text{\{ }}1, \ldots ,m{\text{\} }}$, на которых у Консерватора есть выигрышная стратегия в k раундах).

2. СПЕКТРЫ ФОРМУЛ

Мы изучаем вероятности истинности формул первого порядка на биномиальном случайном графе $G(n,p)$ [7, 8]. Множество вершин этого графа – ${\text{\{ }}1, \ldots ,n{\text{\} }}$, а ребра проводятся независимо с вероятностью p каждое. Иными словами, для любого графа $G = ({\text{\{ }}1, \ldots ,n{\text{\} }},E)$

Говорят, что случайный граф $G(n,p)$ подчиняется закону нуля или единицы, если для любой формулы первого порядка φ либо

либо

(здесь и далее мы пишем $G \vDash \varphi $, если формула φ истинна на графе G). Заметим, что упомянутая теорема из предыдущего раздела утверждает справедливость закона 0 или 1 для случайного графа $G\left( {n,\frac{1}{2}} \right)$. Легко заметить [5], что закон 0 или 1 справедлив и для всех p таких, что для любого $\alpha > 0$ выполнено $min{\text{\{ }}p,1 - p{\text{\} }}{{n}^{\alpha }} \to \infty $, $n \to \infty $, в силу истинности (с асимптотической вероятностью 1) всех аксиом расширения.

Если же $p = {{n}^{{ - \alpha }}}$, $\alpha > 0$, то закон 0 или 1 справедлив тогда и только тогда, когда $\alpha $ – иррационально или $\alpha > 1$ и $\alpha \notin \left\{ {1 + \frac{1}{m},m \in \mathbb{N}} \right\}$ [9]. При ограничении на кванторную глубину формул закон становится справедлив и для некоторых рациональных $\alpha \in (0,1]$ и $\alpha = 1 + \frac{1}{m}$ (см., например, [10, 11]). Говорят, что случайный граф $G(n,p)$ подчиняется k-закону нуля или единицы, если для любой формулы первого порядка φ с ${\mathbf{q}}(\varphi ) \leqslant k$ либо $\mathop {lim}\limits_{n \to \infty } {\text{P}}(G(n,p) \vDash \varphi ) = 1,$ либо $\mathop {lim}\limits_{n \to \infty } {\text{P}}(G(n,p) \vDash \varphi )$ = 0. В [11] доказано, что множество таких $m \in \mathbb{N}$, что случайный граф $G(n,{{n}^{{ - 1 - 1/m}}})$ не подчиняется k-закону нуля или единицы, конечно. Множество $S(k)$ всех таких $\alpha > 0$, что случайный граф $G(n,{{n}^{{ - \alpha }}})$ не подчиняется k-закону нуля или единицы, называется k-спектром. Таким образом, возникает вопрос: а бесконечно ли множество $S(k)$ хоть для каких-то k? Ясно, что если $S(k)$ бесконечно для некоторого k, то $S(\ell )$ также бесконечно для всех $\ell > k$. В [12] Дж. Спенсер доказал, что k-спектр бесконечен при $k \geqslant 14$. В [10] доказано, что $S(3) \cap (0,1) = \phi $ и $S(4) \cap (0,1{\text{/}}2) = \phi .$ В [13] приведен пример такой формулы первого порядка φ кванторной глубины 5, что ${\text{P}}(G(n,{{n}^{{ - \alpha }}}) \vDash \varphi )$ не стремится ни к 0, ни к 1 для бесконечно многих $\alpha $. Итак, минимальное k, при котором множество $S(k)$ бесконечно, равно 4 или 5.

Нам удалось доказать, что минимальное k, при котором k-спектр бесконечен, равно 5, что равносильно следующей теореме.

Теорема 1. Множество $S(4)$ конечно.

Идея доказательства. В прежней работе [14] нам удалось доказать, что множество $S(4)$ не содержит ни одной предельной точки кроме, быть может, 1/2 и 3/5. Теперь мы доказали, что и 1/2, 3/5 не являются предельными точками спектра. Для доказательства этого утверждения достаточно показать, что для некоторого $\varepsilon > 0$ случайный граф $G(n,{{n}^{{ - \alpha }}})$ подчиняется 4-закону 0 или 1 для всех $\alpha \in (1{\text{/}}2,1{\text{/}}2 + \varepsilon )$ и $\alpha \in (3{\text{/}}5,3{\text{/}}5 + \varepsilon )$ (пустота спектра для некоторой левой окрестности любой предельной точки доказана в [9]). Последнее утверждение мы доказали с помощью следствия из теоремы Эренфойхта и следующей леммы.

Лемма 1. Существует $\varepsilon > 0$ такое, что для любого

с вероятностью, стремящейся к 1, у Консерватора есть выигрышная стратегия в 4 раундах в игре Эренфойхта на графах $G(n,{{n}^{{ - \alpha }}})$, $G(m,{{m}^{{ - \alpha }}})$ при n, $m \to \infty $.