{
  "id": "math/0401307",
  "version": "v2",
  "published": "2004-01-22T23:20:06.000Z",
  "updated": "2004-03-31T01:33:16.000Z",
  "title": "Succinct Definitions in the First Order Theory of Graphs",
  "authors": [
    "Oleg Pikhurko",
    "Joel Spencer",
    "Oleg Verbitsky"
  ],
  "comment": "41 pages, Version 2 (small corrections)",
  "categories": [
    "math.LO",
    "math.CO"
  ],
  "abstract": "We say that a first order sentence A defines a graph G if A is true on G but false on any graph non-isomorphic to G. Let L(G) (resp. D(G)) denote the minimum length (resp. quantifier rank) of a such sentence. We define the succinctness function s(n) (resp. its variant q(n)) to be the minimum L(G) (resp. D(G)) over all graphs on n vertices. We prove that s(n) and q(n) may be so small that for no general recursive function f we can have f(s(n))\\ge n for all n. However, for the function q^*(n)=\\max_{i\\le n}q(i), which is the least monotone nondecreasing function bounding q(n) from above, we have q^*(n)=(1+o(1))\\log^*n, where \\log^*n equals the minimum number of iterations of the binary logarithm sufficient to lower n below 1. We show an upper bound q(n)<\\log^*n+5 even under the restriction of the class of graphs to trees. Under this restriction, for q(n) we also have a matching lower bound. We show a relationship D(G)\\ge(1-o(1))\\log^*L(G) and prove, using the upper bound for q(n), that this relationship is tight. For a non-negative integer a, let D_a(G) and q_a(n) denote the analogs of D(G) and q(n) for defining formulas in the negation normal form with at most a quantifier alternations in any sequence of nested quantifiers. We show a superrecursive gap between D_0(G) and D_3(G) and hence between D_0(G) and D(G). Despite it, for q_0(n) we still have a kind of log-star upper bound: q_0(n)\\le2\\log^*n+O(1) for infinitely many n.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2004-03-31T01:33:16.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03C10",
      "03C13",
      "05C60"
    ],
    "keywords": [
      "first order theory",
      "succinct definitions",
      "binary logarithm sufficient",
      "log-star upper bound",
      "first order sentence"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 41,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2004math......1307P"
    }
  }
}