# 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. arXiv: math/9512228 DOI: 10.1016/0168-0072(95)00071-2 MR: 1416640 -
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} }