{
  "id": "math/0405326",
  "version": "v2",
  "published": "2004-05-17T13:16:18.000Z",
  "updated": "2005-12-22T15:56:14.000Z",
  "title": "Definitions with no quantifier alternation",
  "authors": [
    "Oleg Pikhurko",
    "Joel Spencer",
    "Oleg Verbitsky"
  ],
  "comment": "24 pages, we complement the lower bound proved in the first version with a tight upper bound. The title of the paper has been changed",
  "categories": [
    "math.LO"
  ],
  "abstract": "Let $D(G)$ be the minimum quantifier depth of a first order sentence $\\Phi$ that defines a graph $G$ up to isomorphism. Let $D_0(G)$ be the version of $D(G)$ where we do not allow quantifier alternations in $\\Phi$. Define $q_0(n)$ to be the minimum of $D_0(G)$ over all graphs $G$ of order $n$. We prove that for all $n$ we have $\\log^*n-\\log^*\\log^*n-1\\le q_0(n)\\le \\log^*n+22$, where $\\log^*n$ is equal to the minimum number of iterations of the binary logarithm needed to bring $n$ to 1 or below. The upper bound is obtained by constructing special graphs with modular decomposition of very small depth.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2005-12-22T15:56:14.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03C13"
    ],
    "keywords": [
      "quantifier alternation",
      "definitions",
      "minimum quantifier depth",
      "first order sentence",
      "modular decomposition"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 24,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2004math......5326P"
    }
  }
}