First order sentences and the evolution of random graphs

Gabor Tardos

Hungarian Academy of Sciences and DIMACS Center, Rutgers University

November 3,
refreshments at 3:45pm


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 0-1 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 0-1 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(at-sign)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

Page loaded on October 19, 1999 at 04:23 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.