First order distinguishability of sparse random graphs

Tal Hershko, Maksim Zhukovskii

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…