Mathematics – Combinatorics
Scientific paper
2009-04-16
Mathematics
Combinatorics
39 pages
Scientific paper
The classical zero-one law for first-order logic on random graphs says that for any first-order sentence $\phi$ in the theory of graphs, as n approaches infinity, the probability that the random graph G(n, p) satisfies $\phi$ 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 $\phi$, there are two rational numbers a_0, a_1, such that for i in {0,1}, as n approaches infinity, the probability that the random graph G(2n+i, p) satisfies $\phi$ approaches a_i. 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.
Kolaitis Phokion G.
Kopparty Swastik
No associations
LandOfFree
Random Graphs and the Parity Quantifier does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Random Graphs and the Parity Quantifier, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random Graphs and the Parity Quantifier will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-464576