Доклады Российской академии наук. Математика, информатика, процессы управления, 2020, T. 494, № 1, стр. 35-37

Изучение предельного поведения вероятностей истинности предложений первого порядка для случайных графов было заложено в работе 1969 г. [1]. В этой работе (тот же результат был независимо доказан в 1976 г. в [2]) было доказано, что для любого предложения первого порядка [3, 4] на графах (т.е. сигнатура состоит из двух предикатных символов ~, =, обозначающих смежность вершин и равенство вершин соответственно) доля графов на множестве вершин $[n]: = \{ 1, \ldots ,n\} $, для которых это предложение истинно, стремится к 0 или 1 при $n \to \infty $. Другими словами, вероятность истинности предложения на биномиальном случайном графе $G(n,1{\text{/}}2)$ стремится либо к 0, либо к 1. Напомним, что биномиальный случайный граф $G(n,p)$ [5], в котором любая пара вершин из [n] смежна с вероятностью p независимо от всех остальных, является наиболее изученной и наиболее востребованной с точки зрения приложений в комбинаторике моделью случайного графа.

Будем говорить, что (некоторый) случайный граф G_n на множестве вершин $[n]$ подчиняется закону нуля или единицы для логики $\mathcal{L}$, если для любого предложения из $\mathcal{L}$ вероятность истинности этого предложения на G_n стремится либо к 0, либо к 1 при $n \to \infty $.

Множество работ было посвящено обобщению упомянутого результата для других вероятностей проведения ребра p и более широких языков (см., например, [5, 6]). Заметим, что изучение логических законов для случайных графов имеет прозрачную мотивацию. Так, с точки зрения приложений, разумно изучать сложность проверки графовых свойств не только в худшем случае, но и в среднем (при этом распределение может быть подобрано в соответствии с требованиями, которые накладываются на модель случайного графа). Таким образом, если выполнен закон 0 или 1 для логики $\mathcal{L}$, то с точки зрения предложений из $\mathcal{L}$ случайный граф “устроен” тривиальным образом. Но так ли это в случае логики первого порядка и более “естественных” моделей случайного графа?

Наиболее известными моделями реальных сетей является семейство рекурсивных случайных графов, среди которых стоит выделить равномерную модель и модель предпочтительного присоединения, которым и посвящена данная работа (определение этих и других рекурсивных моделей, а также некоторую историю их исследования можно найти, например, в [5, 6]). Под рекурсивной последовательностью графов мы понимаем последовательность графов ${{G}_{n}},$ $n \in \mathbb{N}$, такую что граф ${{G}_{{n + 1}}}$ получается из графа G_n с помощью добавления одной вершины и проведения из нее нескольких ребер в уже имеющиеся вершины (при этом мы предполагаем, что две вершины могут соединяться только одним ребром), которые выбираются в соответствии с некоторым вероятностным распределением.

Параметром в обеих моделях будет служить натуральное число m, равное количеству ребер, добавляемых на каждом шаге. Определим сперва рекурсивный равномерный случайный граф ${{\mathcal{G}}_{{n,m}}}$, $n \in \{ m,m + 1, \ldots \} $. Пусть ${{\mathcal{G}}_{{m,m}}}$ – это полный граф на множестве вершин [m]. Случайный граф ${{\mathcal{G}}_{{n + 1,m}}}$, $n \geqslant m$, получается из ${{\mathcal{G}}_{{n,m}}}$ добавлением вершины n + 1 и m ребер, из нее исходящих и соединенных с m различными вершинами, выбранными равномерно из [n]. Частным случаем этой модели при m = 1 является случайное рекурсивное дерево [9]. Случайный граф предпочтительного присоединения (известный как случайный граф Боллобаша–Риордана) ${{\mathcal{H}}_{n}}$, $n \in \{ 2,3, \ldots \} $, определяется следующим образом: ${{\mathcal{H}}_{2}}$ – это граф на множестве вершин {1, 2} с одним ребром; ${{\mathcal{H}}_{{n + 1}}}$ получается из ${{\mathcal{H}}_{n}}$ добавлением вершины n + 1 и одного ребра, проведенного в вершину, вероятность выбора которой пропорциональна ее степени, т.е. ${\text{P}}(n + 1$ ~ u в ${{\mathcal{H}}_{{n + 1}}}) = \mathop {{\text{deg}}}\nolimits_{{{\mathcal{H}}_{n}}} u{\text{/}}(2n - 2)$. Заметим, что в обобщенной модели Боллобаша–Риордана тоже присутствует параметр $m$. В рассматриваемом нами случае m = 1.

Одним из основных инструментов доказательства законов 0 или 1 для логики первого порядка является игра Эренфойхта (см., например, [5, 6]). Свести доказательство законов к упомянутой игре становится возможным благодаря следующему широко известному результату о связи между элементарной эквивалентностью и игрой.

Теорема 1 (А. Эренфойхт, 1960 [10]). Пусть даны два графа ${{H}_{1}}$ и ${{H}_{2}}$ и некоторое натуральное число k. Тогда не существует предложения первого порядка кванторной глубиной k, различающего графы ${{H}_{1}}$ и ${{H}_{2}}$ (т.е. истинного на одном графе и ложного на другом), тогда и только тогда, когда Консерватор имеет выигрышную стратегию в игре Эренфойхта на графах ${{H}_{1}}$ и ${{H}_{2}}$ в $k$ раундах.

Эта теорема имеет следствие, связывающее закон 0 или 1 и игру Эренфойхта (см., например, [5]): случайный граф G_n подчиняется закону 0 или 1 для логики первого порядка тогда и только тогда, когда для любого $r \in \mathbb{N}$ с вероятностью, стремящейся к 1 при $n,m \to \infty $, Консерватор имеет выигрышную стратегию в игре Эренфойхта на графах ${{G}_{n}},{{G}_{m}}$ в $r$ раундах.

Пусть T – дерево с корнем R, а ${v}$ – сын $R$. Будем обозначать ${{T}_{{v}}}$ поддерево дерева T с корнем ${v}$, содержащее всех наследников вершины ${v}$ (т.е. вершины, которые соединены с ${v}$ путем, не содержащим R). Пусть $r,a \in \mathbb{N}$. Будем говорить, что дерево T обладает (r, a)-свойством, если для любого укорененного дерева F на не более $a$ вершинах в дереве T найдется такая вершина R, что у нее есть хотя бы r сыновей ${{{v}}_{1}}, \ldots ,{{{v}}_{r}}$, “отрезающих” от T деревья ${{T}_{{{{{v}}_{1}}}}}, \ldots ,{{T}_{{{{{v}}_{r}}}}}$, изоморфные F (изоморфизм сохраняет корень).

В [11] доказан закон 0 или 1 для равномерного случайного дерева. В этой работе доказано, что для любого $r \in \mathbb{N}$ существует такое $a(r)$, что если два дерева обладают $(r,a(r))$-свойством, то Консерватор побеждает в игре Эренфойхта на этих двух деревьях в r раундах. Мы доказали, что для любого $r$ с вероятностью, стремящейся к 1, $(r,a(r))$-свойство выполнено и для модели равномерного присоединения с m = 1, и для рассматриваемой модели предпочтительного присоединения, откуда незамедлительно следует закон 0 или 1.

Теорема 2. Случайные графы ${{\mathcal{G}}_{{n,1}}}$ и ${{\mathcal{H}}_{n}}$ подчиняются закону 0 или 1 для логики первого порядка.

Нам удалось доказать, что при $m \geqslant 2$ случайный граф ${{\mathcal{G}}_{{n,m}}}$ не подчиняется закону 0 или 1. Так, при m = 2 вероятность того, что случайный граф содержит хотя бы K (для некоторой константы K) копий даймонд-графа (графа на 4 вершинах с 5 ребрами), стремится к числу, отличному от 0 или 1. При m > 2 справедливо аналогичное утверждение, только вместо даймонд-графа надо рассмотреть полный граф на m + 1 вершине.

Заметим, что для рассматриваемых предложений вероятность не сходится ни к 0, ни к 1, но у нее есть предел. В этой связи встает вопрос о сходимости. Будем говорить, что случайный граф G_n подчиняется закону сходимости для логики $\mathcal{L}$, если для любого предложения из $\mathcal{L}$ вероятность его истинности на G_n сходится к некоторому пределу при $n \to \infty $. Нам не удалось доказать закон сходимости для логики первого порядка для ${{\mathcal{G}}_{{n,m}}}$. Тем не менее, нам удалось доказать, что сходимость есть для предложений с не очень большой кванторной глубиной [4] (под кванторной глубиной, грубо говоря, подразумевается максимальное количество вложенных кванторов в формуле).

Теорема 3. Случайный граф ${{\mathcal{C}}_{{n,m}}}$ подчиняется закону сходимости для предложений первого порядка, кванторная глубина которых не больше чем m.

Этот результат тоже доказывается с помощью теоремы 1, а также с помощью следующей доказанной нами леммы о локальной структуре случайного графа ${{\mathcal{G}}_{{n,m}}}$.

Лемма 1. Для любого $a \in \mathbb{N}$ найдутся n₀, ${{N}_{0}} \in \mathbb{N}$, такие что с вероятностью, стремящейся к 1 (при $n \to \infty $), выполнены следующие условия:

1. Любой цикл с не более чем a вершинами либо полностью лежит в ${{\mathcal{G}}_{{{{N}_{0}},m}}}$, либо находится на расстоянии, большем a, от ${{\mathcal{G}}_{{{{n}_{0}},m}}}$.

2. Любой путь длины не более a, соединяющий две вершины из ${{\mathcal{G}}_{{{{n}_{0}},m}}}$, лежит целиком в ${{\mathcal{G}}_{{{{N}_{0}},m}}}$.

3. Любые два цикла на не более чем a вершинах, лежащие в ${{\mathcal{G}}_{{n,m}}}{\backslash }{{\mathcal{G}}_{{{{n}_{0}},m}}}$, находятся на расстоянии большем a друг от друга.

4. Для любого $b \leqslant a$ существуют как минимум m циклов длины $b$ с вершинами в ${{\mathcal{G}}_{{n,m}}}{\backslash }{{\mathcal{G}}_{{{{n}_{0}},m}}}$.

5. Степень любой вершины из ${{\mathcal{G}}_{{{{N}_{0}},m}}}$ в графе ${{\mathcal{G}}_{{n,m}}}$ не меньше ${{N}_{0}} + m$.

От условия на ограниченность кванторной глубины можно отказаться, если ввести ограничение на максимальную степень случайного графа. А именно, рассмотрим следующую модель. Как и в равномерной модели на шаге n + 1 будем проводить m ребер в вершины, выбранные равномерно, но не из всего множества вершин [n], а из тех вершин из [n], степени которых меньше заданного параметра d. Поскольку на каждом шаге суммарная степень всех вершин увеличивается на 2m, мы предполагаем, что $d > 2m$. Будем обозначать такой случайный граф ${{\mathcal{G}}_{{n,m,d}}}$. Итак, нами получен следующий результат.

Теорема 4. Для любых $m \geqslant 1$ и $d > 2m$ случайный граф ${{\mathcal{G}}_{{n,m,d}}}$ подчиняется закону сходимости для логики первого порядка.