First-Order Distinguishability of Sparse Random Graphs

We study the problem of distinguishing between two independent samples G n 1 , G n 2 Gₙ¹,Gₙ² 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 ) α ∈ (0,1) alpha element of left parenthesis 0 comma 1 right parenthesis , G ( n , n − α ) G(n,n-α) upper G left parenthesis n comma n Superscript negative alpha Baseline right parenthesis obeys FO zero-one law if and only if α α alpha is irrational. Therefore, for irrational α ∈ ( 0 , 1 ) α ∈ (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