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)

@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}
}