Zero-one law in binomial random graph model $G(n,p)$

Question

Consider the binomial random graph model $G(n,p)$ with $0<p<1$. We say that $G(n,p)$ satisfies the Zero-One law if for every first order property $Q$ one has $\lim\limits_{n \rightarrow \infty} Pr(G(n,p)~ has~ property~ Q) \in \{ 0, 1 \}$. And as it has been proved by Shelah and Spencer in 1988, it doesn't satisfy the Zero-One law if $p(n)$ equals to one of the functions $n^{-1 - \frac{1}{k}}$, $n^{-1}$, $n^{-1} ln n$ and $n^{- \alpha}$ for rational $0< \alpha < 1$.

Now one of the interesting questions which seems common here to ask is that if we take $p(n) = \sqrt{n^{-1} ln n}$, will zero-one law still not be satisfied? or will satisfy? and why?

Thanks!

Answer 1

I'm not an expert on that specific question, and it's certainly the most difficult regime of $\mathcal{G}(n,p)$ to understand, so I'll just show the path.

First, the question can be generalized as $p = n^{-\alpha} + w(n)$, with the question taking the specific instance of $\alpha = 1/2$ and $w(n) = (\ln n )^{1/2}$. The first thing to understand is the Shelah-Spencer result about $\mathcal{G}(n,n^{-\alpha})$. Fundamentally, it depends on the rationality of the exponent because the result depends on the threshold function for the appearance of certain subgraphs, in other words on the number of copies (asymptotically none, a finite number or infinitely many) of certain logical types in the graph. Precisely, for a subgraph $H$ the number of copies of $H$ is $O(n^v \cdot p^{e}) = O(n^{v-e\alpha})$, which should give an intuition of why some things break when $\alpha$ is rational.

Now close to the rational power of $n$, the situation is quite tricky and full of subtleties, but there's a treatment in Spencer's wonderful book [1], in section 8.4.

[0] Shelah, Saharon, and Joel Spencer. "Zero-one laws for sparse random graphs." Journal of the American Mathematical Society 1.1 (1988): 97-115.

[1] Spencer, Joel. The strange logic of random graphs. Vol. 22. Springer Science & Business Media, 2001.