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.