On the convergence of probabilities of the random graph properties expressed by first-order formulae with a bounded quantifier depth (Q488867): Difference between revisions

Let \(G(n,p(n))\) be an Erdős-Rényi random graph. When \(p(n)\) is a constant, it is well known that every first-order property \(\wp\) (i.e. a property expressible as a sentence in first-order logic) satisfies a zero-one law in the sense that either \(\lim_{n\rightarrow\infty}\mathbb{P}(G(n,p(n))\in \wp)=1\) or \(\lim_{n\rightarrow\infty}\mathbb{P}(G(n,p(n))\in \wp)=0\). In fact, this result also holds when \(p(n)=n^{-\alpha}\) for \(\alpha\in \mathbb{R}\backslash \mathbb{Q}\) (but not for rational \(\alpha\)). The article under review partially extends these results to the case of properties expressed by formulae with quantifier depth bounded by some number \(k\). More precisely, if \(\alpha=1/(k-2)\), and \({\mathcal L}_{k}={\mathcal L}\cap {\mathcal L}_{k}^{\infty}\) where \({\mathcal L}\) is a subclass of \({\mathcal L}^{\infty}\), all properties expressed by formulae with an infinite number of conjunctions and disjunctions, and \({\mathcal L}_{k}^{\infty}\) is a subclass of \({\mathcal L}^{\infty}\) containing all properties expressed by formulae with quantifier depth bounded by \(k\), then \(\lim_{n\rightarrow\infty}\mathbb{P}(G(n,n^{-\alpha})\in \wp)\) exists for every property \(\wp\in {\mathcal L}_{k}\). The proofs use, amongst other things, results related to the Ehrenfeucht game and on the distribution of small subgraphs.