THRESHOLD SPECTRA FOR RANDOM GRAPHS.

Saharon Shelah, Joe Spencer

Research output: Contribution to journalConference articlepeer-review

Abstract

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 languageEnglish (US)
Pages (from-to)421-424
Number of pages4
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 1987

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'THRESHOLD SPECTRA FOR RANDOM GRAPHS.'. Together they form a unique fingerprint.

Cite this