Random Graphs and the Parity Quantifier

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.