Random Graphs and the Parity Quantifier

Thursday, October 7, 2010 -
2:30pm to 4:30pm
The classical zero-one law for first-order logic on random graphs says that for any first-order sentence $F$ in the theory of graphs, the probability that the random graph $G(n, p)$ satisfies $F$ approaches either 0 or 1 as $n$ grows. It is well known that this law fails to hold for properties involving parity phenomena (oddness/evenness): 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, I will discuss the behavior of FO[parity], first order logic equipped with the parity quantifier, on random graphs. Our main result is a "modular convergence law" which precisely captures the behavior of FO[parity] properties on large random graphs.I will give an overview of this result and its proof. Along the way, we will ask (and answer) some basic, natural questions about the distribution of subgraph counts *mod 2* in random graphs (what is the probability that $G(n,p)$ has: an odd number of triangles? an even number of 4-cycles? an odd number of triangles and an even number of 4-cycles? etc.). Our approach is based on multivariate polynomials over finite fields, in particular, on a variation on the Gowers norm. The proof generalizes the original quantifier elimination approach to the zero-one law, and has analogies with the Razborov-Smolensky method from circuit complexity.Joint work with Phokion Kolaitis.
Swastik Kopparty
Event Location: 
Fine Hall 224