TY - JOUR

T1 - THRESHOLD SPECTRA FOR RANDOM GRAPHS.

AU - Shelah, Saharon

AU - Spencer, Joe

PY - 1987

Y1 - 1987

N2 - Let G equals G(n,p) be the random graph with n vertices and edge probability p and f(n,p,A) be the probability that G has A, where A is a first order property of graphs. The evolution of the random graph is discussed in terms of a spectrum of p equals p(n) where f(n,p,A) changes. A partial characterization of possible spectra is given. When p equals n** minus **+61, alpha irritational, and A is any first order statement, it is shown that lim f(n,p,A) equals 0 or 1.

AB - Let G equals G(n,p) be the random graph with n vertices and edge probability p and f(n,p,A) be the probability that G has A, where A is a first order property of graphs. The evolution of the random graph is discussed in terms of a spectrum of p equals p(n) where f(n,p,A) changes. A partial characterization of possible spectra is given. When p equals n** minus **+61, alpha irritational, and A is any first order statement, it is shown that lim f(n,p,A) equals 0 or 1.

UR - http://www.scopus.com/inward/record.url?scp=0023595649&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023595649&partnerID=8YFLogxK

U2 - 10.1145/28395.28440

DO - 10.1145/28395.28440

M3 - Conference article

AN - SCOPUS:0023595649

SP - 421

EP - 424

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

SN - 0734-9025

ER -