In the random graph G(n,p),p=n^{-a} : if psi has probability 0(n^{-epsilon}) for every epsilon > 0 then it has probability 0(e^{-n^epsilon}) for some epsilon > 0
| dc.creator | Shelah, Saharon | |
| dc.date | 1995-12-15 | |
| dc.date.accessioned | 2026-07-07T09:15:26Z | |
| dc.date.available | 2026-07-07T09:15:26Z | |
| dc.description | 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, ...,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-epsilon}) for some epsilon such that beta >epsilon>0 OR [(beta)] Prob (G(n,p_n) models psi)= O(n^{-epsilon}) for every epsilon>0. Lynch conjectured that in case (beta) we have [(beta^+)] Prob (G(n,p_n) models psi)= O(e^{-n^epsilon}) for some epsilon>0. We prove it here. | |
| dc.identifier | https://arxiv.org/abs/math/9512228 | |
| dc.identifier | http://arxiv.org/abs/math/9512228 | |
| dc.identifier | Ann. Pure Appl. Logic 82 (1996), 97-102 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/153017 | |
| dc.subject | Logic | |
| dc.subject | Combinatorics | |
| dc.title | In the random graph G(n,p),p=n^{-a} : if psi has probability 0(n^{-epsilon}) for every epsilon > 0 then it has probability 0(e^{-n^epsilon}) for some epsilon > 0 | |
| dc.type | text |