Аннотация:
В докладе речь пойдет об асимптотике вероятностей свойств первого
порядка случайного графа Эрдеша–Реньи $G(n,p)$ (в случайном графе
$G(n,p)$ на $n$ вершинах ребра проводятся независимо с
вероятностью $p$). Свойствами первого порядка называются свойства,
выражаемые формулами, записанными на языке первого порядка (в
записи участвуют символы переменных $x,y,x_1,\ldots$ (вершины
графа), символы отношений $\sim$ (символ смежности двух вершин) и
= (символ совпадения двух вершин), логические связки и кванторы).
В 1969 году Ю.В.Глебский, Д.И.Коган, М.И.Лиогонький и
В.А.Таланов (а в 1976 году независимо Р.Фагин) доказали, что
случайный граф $G(n,p)$ подчиняется закону нуля или единицы. А
именно, для любого свойства первого порядка вероятность выполнения
этого свойства стремится либо к 0, либо к 1. Если в качестве
вероятности $p$ выбрать некоторую функцию $p=p(n)$, то закон может
нарушаться. Так, в 1988 году Дж. Спенсер и С. Шелла рассмотрели
$p=n^{-\alpha}$, где $\alpha>0$, и обнаружили удивительный эффект:
при иррациональных $\alpha$ закон нуля или единицы выполнен, а при
рациональных $\alpha\in(0,1]$ - нет. Они получили, кроме того,
исчерпывающий результат для рациональных $\alpha\in(1,\infty)$.
Дальнейшие исследования в области были связаны с уменьшением
множества свойств и рассмотрением всех свойств, выражаемых
формулами первого порядка с ограниченной числом $k$ кванторной
глубиной (кванторной глубиной формулы называется максимальная
длина цепочки вложенных кванторов в этой формуле). Если
вероятность выполнения любого свойства из такого множества
стремится либо к 0, либо к 1, то говорят, что выполнен $k$-закон
нуля или единицы. Для различных $k\in\mathbb{N}$ нами были найдены
диапазоны значений $\alpha\in(0,1)$, при которых случайный граф
$G(n,n^{-\alpha})$ подчиняется $k$-закону нуля или единицы. Были
найдены, кроме того, наименьшее и наибольшее в интервале $(0,1)$
значения $\alpha$, при которых нарушается $k$-закон.
|
