95-52 In the random graph ...

DIMACS TR: 95-52

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

(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.

We prove it here.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-52.ps.gz

DIMACS Home Page