## 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 such a 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 bo so small that for no general recursive function f we can have f(s(n)) ≥ n for all n. However, for the function q^{*}(n) = max_{i≤n} q(i), which is the least nondecreasing function bounding q(n) from above we have q^{*} = (1 +o(1)) log^{*} n, where log^{*} n equals the minimum number of iterations of the binary logarithm sufficient to lower n to 1 or below. We show an upper bound q(n) < log^{*} n + 5 even under the restriciton of the class of graphs to trees. Under this restriction, for q(n) we laso have a matching lower bound. We show a relationship D(G) ≥ (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 this, for q_{0}(n) we still have a kind of log-star upper bound: q_{0}(n) ≤ 2 log^{*} n + O(1) for definitely many n.

Original language | English (US) |
---|---|

Pages (from-to) | 74-109 |

Number of pages | 36 |

Journal | Annals of Pure and Applied Logic |

Volume | 139 |

Issue number | 1-3 |

DOIs | |

State | Published - May 2006 |

## Keywords

- Definability
- Finite graphs
- First order logic
- Turing machine simulation

## ASJC Scopus subject areas

- Logic