## 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