On Thursday, May 13, 2010
Swastik Kopparty (M.I.T.) will speak on 
Random graphs and the parity quantifier

Abstract:
The classical zero-one law for first-order logic on random graphs says that for
any first-order graph property $Q$, as $n$ approaches infinity, the probability
that the random graph $G(n, p)$ satisfies $Q$ approaches either 0 or 1. It is
well known that this law fails to hold for any formalism that can express the
parity quantifier: for certain properties, the probability that $G(n, p)$
satisfies the property need not converge, and for others the limit may be
strictly between 0 and 1. In this talk, we describe the limiting behavior of
properties definable in first order logic augmented with the parity quantifier,
FO[parity], over $G(n, p)$, which gently eludes the above hurdles.
Specifically, we establish the following ``modular convergence law":

For every FO[parity] property $Q$, there are two rational numbers $ a_0, a_1$,
such that for $i$ in $\{0,1\}$, as $n$ approaches infinity, the probability
that the random graph $G(2n+i, p)$ satisfies $Q$ approaches $a_i$.

Our proof generalizes the original quantifier elimination approach to the
zero-one law, and is based on polynomials over finite fields.

Joint work with Phokion Kolaitis.