FIRST-ORDER DISTINGUISHABILITY OF SPARSE RANDOM GRAPHS

Abstract We study the problem of distinguishing between two independent samples G n 1 , G n 2 $\mathbf {G}_n^1,\mathbf {G}_n^2$ bold upper G Subscript n Superscript 1 Baseline comma bold upper G Subscript n Superscript 2 of a binomial random graph G ( n , p ) $G(n,p)$ upper G left parenthesis n comma p right parenthesis by first-order (FO) sentences. Shelah and Spencer proved that, for a constant α ∈ ( 0 , 1 ) $\alpha \in (0,1)$ alpha element of left parenthesis 0 comma 1 right parenthesis , G ( n , n − α ) $G(n,n^{-\alpha })$ upper G left parenthesis n comma n Superscript negative alpha Baseline right parenthesis obeys FO zero-one law if and only if α $\alpha $ alpha is irrational. Therefore, for irrational α ∈ ( 0 , 1 ) $\alpha \in (0,1)$ alpha element of left parenthesis 0 comma 1 right parenthesis , any fixed FO sentence does not distinguish between G n 1 , G n 2