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.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))≥n for all n. However, for the function q∗(n)=maxi≤nq(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.We show an upper bound q(n)