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

The author and \textit{J. Spencer} [J. Am. Math. Soc. 1, No. 1, 97-115 (1988; Zbl 0647.05051)] 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 is \([n] = \{1, \dots, n\}\), the edges are drawn independently, probability of edge is \(p_n)\). One may wonder what can we say on sentences \(\psi\) for which \(\text{Prob} (G(n,p_n) \models \psi)\) converge to zero; \textit{J. F. Lynch} [Random. Struct. Algorithms 3, No. 1, 33-53 (1992; Zbl 0754.05061)] asked the question and did the analysis, getting (for every \(\psi)\) \((\alpha) \text{ Prob} (G(n,p_n) \models \psi) = cn^{-\beta} + O(n^{-\beta - \varepsilon})\) for some \(\beta, \varepsilon\) such that \(\beta > \varepsilon > 0\) or \((\beta) \text{ Prob} (G(n,p_n) \models \psi) = O(n^{-\varepsilon})\) for every \(\varepsilon > 0\). Lynch conjectured that in case \((\beta)\) we have \((\beta^+) \text{ Prob} (G(n,p_n) \models \psi) = O(e^{-n^\varepsilon})\) for some \(\varepsilon > 0\). We prove it here.