On the Limit Probabilities of the First Order Properties of Graphs
Speaker:
Lubos Thoma
DIMACS postdoc
Place:
CoRE Building, Room 431
Busch Campus, Rutgers University.
Time:
3:30 - 4:30 PM
Wednesday, May 28, 1997
Abstract:
Consider the random graph $G(n,p),$
where $p=p(n)$ is any threshold function satisfying
$p(n) = \Theta(\ln n / n).$
Let $\psi$ be any sentence from the first order language
of graphs. We give a full characterization of the limit
values $\lim_{n\to\infy} Prob( G(n,p) has \psi).$