2009/04/16 by Phokion G. Kolaitis, Swastik Kopparty, Kolaitis, Phokion G. +1
Mathematics · #03C80 #05C80 #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO) #math.CO #math.LO #msc:03C80 #msc:05C80
paper · pdf · doi:10.48550/arxiv.0904.2436
39 pages
arxiv created 2009/04/16 · arxiv updated 2009/12/01
The classical zero-one law for first-order logic on random graphs says that for any first-order sentence ϕ in the theory of graphs, as n approaches infinity, the probability that the random graph G(n, p) satisfies ϕ 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 paper, we capture the limiting behavior of properties definable in first order logic augmented with the parity quantier, FO[parity], over G(n, p), thus eluding the above hurdles. Specifically, we establish the following "modular convergence law": For every FO[parity] sentence ϕ, there are two rational numbers a0, a1, such that for i in 0,1, as n approaches infinity, the probability that the random graph G(2n+i, p) satisfies ϕ approaches ai. Our results also extend appropriately to first order logic equipped with Mod-q quantiers for prime q. Our approach is based on multivariate polynomials over finite fields, in particular, on a new generalization of the Gowers norm. The proof generalizes the original quantifier elimination approach to the zero-one law, and has analogies with the Razborov-Smolensky method for lower bounds for AC0 with parity gates.