First order distinguishability of sparse random graphs

We study the problem of distinguishing between two independent samples [EQUATION], [EQUATION] 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 [EQUATION] with asymptotical probability 1 (w.h.p.) as n → ∞. We show that the minimum quantifier depth k_α of a FO sentence [EQUATION] distinguishing between [EQUATION] depends on how closely α can be approximated by rationals:

• for all non-Liouville α ∈ (0, 1), k_α = Ω(ln ln ln n) w.h.p.;

• there are irrational α ∈ (0, 1) with k_α that grow arbitrarily slowly w.h.p.;

• [EQUATION] 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.