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