Random Graphs and the Parity Quantifier
| dc.creator | Kolaitis, Phokion G. | |
| dc.creator | Kopparty, Swastik | |
| dc.date | 2009-04-16 | |
| dc.date.accessioned | 2026-07-07T13:04:57Z | |
| dc.date.available | 2026-07-07T13:04:57Z | |
| dc.description | 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 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 $ϕ$ 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. | |
| dc.description | 39 pages | |
| dc.identifier | https://arxiv.org/abs/0904.2436 | |
| dc.identifier | http://arxiv.org/abs/0904.2436 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/227347 | |
| dc.subject | Combinatorics | |
| dc.subject | Logic | |
| dc.subject | 05C80; 03C80 | |
| dc.title | Random Graphs and the Parity Quantifier | |
| dc.type | text |