FIRST-ORDER DISTINGUISHABILITY OF SPARSE RANDOM GRAPHS

Abstract

We study the problem of distinguishing between two independent samples

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 $\mathbf {G}_n^1,\mathbf {G}_n^2$ bold upper G Subscript n Superscript 1 Baseline comma bold upper G Subscript n Superscript 2

with asymptotical probability 1 (w.h.p.) as

n → ∞ $n\to \infty $ n right arrow infinity

. We show that the minimum quantifier depth

k α $\mathbf {k}_{\alpha }$ bold k Subscript alpha

of an FO sentence

φ = φ ( G n 1 , G n 2 ) $\varphi =\varphi (\mathbf {G}_n^1,\mathbf {G}_n^2)$ phi equals phi left parenthesis bold upper G Subscript n Superscript 1 Baseline comma bold upper G Subscript n Superscript 2 Baseline right parenthesis

distinguishing between

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

depends on how closely

α $\alpha $ alpha

can be approximated by rationals:

•

for all non-Liouville

α ∈ ( 0 , 1 ) $\alpha \in (0,1)$ alpha element of left parenthesis 0 comma 1 right parenthesis

,

k α = Ω ( ln ⁡ ln ⁡ ln ⁡ n ) $\mathbf {k}_{\alpha }=\Omega (\ln \ln \ln n)$ bold k Subscript alpha Baseline equals normal upper Omega left parenthesis ln ln ln n right parenthesis

w.h.p.;

•

there are irrational

α ∈ ( 0 , 1 ) $\alpha \in (0,1)$ alpha element of left parenthesis 0 comma 1 right parenthesis

with

k α $\mathbf {k}_{\alpha }$ bold k Subscript alpha

that grow arbitrarily slowly w.h.p.;

•

k α = O p ( ln ⁡ n ln ⁡ ln ⁡ n ) $\mathbf {k}_{\alpha }=O_p(\frac {\ln n}{\ln \ln n})$ bold k Subscript alpha Baseline equals upper O Subscript p Baseline left parenthesis StartFraction ln n Over ln ln n EndFraction right parenthesis

for all

α ∈ ( 0 , 1 ) $\alpha \in (0,1)$ alpha element of left parenthesis 0 comma 1 right parenthesis

.