Succinct definitions in the first order theory of graphs

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. ve that s ( n ) and q ( n ) may be 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 ∗ ( n ) = ( 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. w 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. w a relationship D ( G ) ≥ ( 1 − o ( 1 ) ) log ∗ L ( G ) and prove, using the upper bound for q ( n ) , that this relationship is tight. 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 infinitely many  n .