{
  "id": "0904.2436",
  "version": "v1",
  "published": "2009-04-16T06:33:25.000Z",
  "updated": "2009-04-16T06:33:25.000Z",
  "title": "Random Graphs and the Parity Quantifier",
  "authors": [
    "Phokion G. Kolaitis",
    "Swastik Kopparty"
  ],
  "comment": "39 pages",
  "categories": [
    "math.CO",
    "math.LO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-04-16T06:33:25.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "03C80"
    ],
    "keywords": [
      "parity quantifier",
      "first order logic",
      "approaches infinity",
      "zero-one law",
      "original quantifier elimination approach"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 39,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0904.2436K"
    }
  }
}