DIMACS TR: 97-35
On the Limit Values of Probabilities for
the First Order Properties of Graphs
Authors: Joel Spencer and Lubos Thoma
ABSTRACT
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