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

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.

We prove it here.

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

DIMACS Home Page