In the random graph G(n,p), p=n^{-a}:
if F has probability O(n^{-v}) for every v>0,
then it has probability O(e^{-n^v}) for some v>0
Author: Saharon Shelah
ABSTRACT
Shelah Spencer proved the 0-1 law for the random graphs G(n,p(n)),
p(n)=n^{-a}, 0 < a < 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 F for which
Prob[G(n,p(n)) satisfies F} converges to zero.
Lynch asked the question and did the analysis, getting (for every F):
(i) Prob[G(n,p(n)) satisfies F] = cn^{-b}+ O(n^{-b-v})
for some v such
that b>v>0
or
(ii) Prob(G(n,p(n)) satisfies F) = O(n^{-v}) for every v>0.
Lynch conjectured that in case (ii) we have
(++) Prob(G(n,p(n)) satisfies F) = O(e^{-n^v)) for some v>0.
DIMACS Home Page