Аннотация:
В докладе речь пойдет об асимптотике вероятностей свойств первого порядка случайного графа Эрдеша–Реньи $G(n,p)$ (в случайном графе $G(n,p)$ на $n$ вершинах ребра проводятся независимо с вероятностью $p$). Свойствами первого порядка называются свойства, выражаемые формулами, записанными на языке первого порядка (в записи участвуют символы переменных $x,y,x_1,\dots$ (вершины графа), символы отношений $\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$, при которых случайный граф $G(n,n^{-\alpha})$ подчиняется $k$-закону нуля или единицы. Были найдены, кроме того, наименьшее и наибольшее в интервале $(0,1)$ значения $\alpha$, при которых нарушается $k$-закон.
|
