First order sentences and the evolution of random graphs
Gabor Tardos
Hungarian Academy of Sciences and DIMACS Center, Rutgers University
November 3,
4:15pm
refreshments at 3:45pm
2338
ABSTRACT

We study the behavior of the random graph with respect
to first order statements.
First order statements are built from the atomic formulae $x=y$ and
$x\sim y$ ($x$ is connected to $y$) with logical connectives and
quantors ranging
over the vertices of the graph. A simple first order
statement is that every edge is in a triangle. This statement
holds almost always for $G(n,n^{\alpha})$ if $\alpha<1/2$ and
holds almost never if $\alpha>1/2$. The limit probability ``jumps''
at $\alpha=1/2$. Here $G(n,p)$ is the random graph with $n$ vertices, whose
edges are present independently with probability $p$.
A celebrated result of Shelah and Spencer from '88 is the
following 01 low: any first order sentence on $G(n,p)$ with
$p=n^{\alpha}$ holds almost always or almost never if $\alpha$
is irrational. We study how this limit probability can depend on $\alpha$.
Surprisingly, for some sentences the limit jumps infinitely often.
We identify a number theoretic and a computational complexity condition,
that together give a complete characterization of the 01 functions that
arise as limits. An interesting consequence of our result
characterizes the unary languages $L$ such that for
some first order sentence the limit probability jumps at exactly the
values $1/2+1/k$ for $k\in L$. These are exactly the unary languages in
the polynomial time hierarchy $PH$.
Most of these results are joint work with Joel Spencer.

Speaker's Contact Info: tardos(atsign)mathinst.hu
Return to seminar home page
Page loaded on October 19, 1999 at 04:23 PM.

Copyright © 199899, Sara C. Billey.
All rights reserved.

