First order distinguishability of sparse random graphs

We study the problem of distinguishing between two independent samples Gₙ¹,Gₙ² of a binomial random graph $G(n,p)$ by first order (FO) sentences. Shelah and Spencer proved that, for a constant α∈(0,1), G(n,n-α) obeys FO zero-one law if and only if α is irrational. Therefore, for irrational α∈(0,1), any fixed FO sentence does not distinguish between Gₙ¹,Gₙ² with asymptotical probability 1 (w.h.p.) as n→∞. We show that the minimum quantifier depth kα of a FO sentence φ=φ(Gₙ¹,Gₙ²) distinguishing between Gₙ¹,Gₙ² depends on how closely α can be approximated by rationals: (1) for all non-Liouville α∈(0,1), kα=Ω(lnlnln n) w.h.p.; (2) there are irrational α∈(0,1) with kα that grow arbitrarily slowly w.h.p.; (3) kα=Oₚ(ln n/lnln n) for all α∈(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.