DIMACS TR: 97-35

On the Limit Values of Probabilities for the First Order Properties of Graphs

Authors: Joel Spencer and Lubos Thoma


Consider the random graph ${\cal G}(n,p),$ where $p=p(n)$ is any threshold function satisfying $p(n) = \Theta(\ln n / n).$ We give a full characterization of the limit values of probabilities of ${\cal G}(n,p)$ having a property $\psi,$ where $\psi$ is any sentence of the first order theory of graphs.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-35.ps.gz
DIMACS Home Page