First order distinguishability of sparse random graphs

We study the problem of distinguishing between two independent samples G(n)(1), 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 is an element of(0, 1), G(n, n(-alpha)) obeys FO zero-one law if and only if alpha is irrational. Therefore, for irrational alpha is an element of(0, 1), any fixed FO sentence does not distinguish between G(n)(1), G(n)(2) with asymptotical probability 1 (w.h.p.) as n ->infinity. We show that the minimum quantifier depth ka of a FO sentence G(n)(1), G(n)(2) = G(n)(1), G(n)(2)(G(n)(1), G(n)(2)) distinguishing between G(n)(1), G(n)(2) depends on how closely a can be approximated by rationals: for all non-Liouville alpha is an element of (0, 1), k(alpha) = Omega(ln ln lnn) w.h.p.; there are irrational alpha is an element of (0, 1) with ka that grow arbitrarily slowly w.h.p.; k(alpha) = Op ( ln n/ln ln n) for all alpha is an element of(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.