### In the random graph $G(n,p),p=n^{-a}$: if $\psi$ has probability $0(n^{-\varepsilon})$ for every $\varepsilon > 0$ then it has probability $0(e^{-n^\varepsilon})$ for some $\varepsilon > 0$

by Shelah. [Sh:551]

Annals Pure and Applied Logic, 1996

Shelah Spencer [ShSp:304] proved the 0-1 law for the random
graphs G(n,p_n), p_n=n^{- alpha}, alpha in (0,1) irrational
(set of nodes in [n]= {1, ...,n}, the edges are drawn
independently, probability of edge is p_n). One may wonder what
can we say on sentences psi for which Prob (G(n,p_n) models psi)
converge to zero, Lynch asked the question and did the analysis,
getting (for every psi):
EITHER [(alpha)] Prob [G(n,p_n) models psi]=cn^{- beta} +
O(n^{- beta-epsilon}) for some epsilon such that
beta >epsilon >0
OR [(beta)] Prob (G(n,p_n) models psi)= O(n^{-epsilon}) for
every epsilon >0 .
Lynch conjectured that in case (beta) we have
[(beta^+)] Prob (G(n,p_n) models psi)= O(e^{-n^epsilon}) for
some epsilon >0 . We prove it here.

Back to the list of publications