First order distinguishability of sparse random graphs

We study the problem of distinguishing between two independent samples ${\mathbf{G}}_n^1,{\mathbf{G}}_n^2$ of a binomial random graph $G(n,p)$ by first order (FO) sentences. Shelah and Spencer proved that, for a constant $\alpha \in (0,1)$, $G(n,n^{-\alpha })$ obeys FO zero-one law if and only if $\alpha$ is irrational. Therefore, for irrational $\alpha \in (0,1)$, any fixed FO sentence does not distinguish between ${\mathbf{G}}_n^1,{\mathbf{G}}_n^2$ with asymptotical probability 1 (w.h.p.) as $n\to \mathrm{\infty }$. We show that the minimum quantifier depth ${\mathbf{k}}_{\alpha }$ of a FO sentence $\phi =\phi ({\mathbf{G}}_n^1,{\mathbf{G}}_n^2)$ distinguishing between ${\mathbf{G}}_n^1,{\mathbf{G}}_n^2$ depends on how closely $\alpha$ can be approximated by rationals: (1) for all non-Liouville $\alpha \in (0,1)$, ${\mathbf{k}}_{\alpha }=\mathrm{\Omega }(\ln \ln \ln n)$ w.h.p.; (2) there are irrational $\alpha \in (0,1)$ with ${\mathbf{k}}_{\alpha }$ that grow arbitrarily slowly w.h.p.; (3) ${\mathbf{k}}_{\alpha }=O_p(\frac{\ln n}{\ln \ln n})$ for all $\alpha \in (0,1)$. The main ingredients in our proofs are a novel randomized algorithm that generates asymmetric strictly balanced graphs as well as a new method to study symmetry groups of randomly perturbed graphs.