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.
|Original language||English (US)|
|Number of pages||4|
|Journal||Conference Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - 1987|
ASJC Scopus subject areas