First order distinguishability of sparse random graphs

We study the problem of distinguishing between two independent samples G 1 n , G 2 n 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

n 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.;

• k α = O p ( ln n ln ln 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.