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.