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
SN - 0734-9025
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
ER -