# Sh:551

• Shelah, S. (1996). In the random graph G(n,p), p=n^{-a}: if \psi has probability O(n^{-\epsilon}) for every \epsilon>0 then it has probability O(e^{-n^\epsilon}) for some \epsilon>0. Ann. Pure Appl. Logic, 82(1), 97–102.
• Abstract:
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,\ldots,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-\varepsilon}) for some \varepsilon such that \beta>\varepsilon>0

OR [(\beta)] Prob(G(n,p_n)\models\psi)= O(n^{-\varepsilon}) for every \varepsilon>0.

Lynch conjectured that in case (\beta) we have

[(\beta^+)] Prob(G(n,p_n)\models\psi)= O(e^{-n^\varepsilon}) for some \varepsilon>0. We prove it here.

• Version 1995-12-22_10 (8p) published version (6p)
Bib entry
@article{Sh:551,
author = {Shelah, Saharon},
title = {{In the random graph $G(n,p)$, $p=n^{-a}$: if $\psi$ has probability $O(n^{-\epsilon})$ for every $\epsilon>0$ then it has probability $O(e^{-n^\epsilon})$ for some $\epsilon>0$}},
journal = {Ann. Pure Appl. Logic},
fjournal = {Annals of Pure and Applied Logic},
volume = {82},
number = {1},
year = {1996},
pages = {97--102},
issn = {0168-0072},
mrnumber = {1416640},
mrclass = {03C13 (05C80 60F20)},
doi = {10.1016/0168-0072(95)00071-2},
note = {\href{https://arxiv.org/abs/math/9512228}{arXiv: math/9512228}},
arxiv_number = {math/9512228}
}