The first order definability of graphs: Upper bounds for quantifier depth
Let D(G) D ( G ) denote the minimum quantifier depth of a first order sentence that defines a graph G up to isomorphism in terms of the adjacency and equality relations. Call two vertices of G similar if they have the same adjacency to any other vertex and denote the maximum number of pairwise similar vertices in G  by ?(G) ? ( G ) . We prove that ?(G)+1?D(G)?max{?(G)+2,(n+5)/2} ? ( G ) + 1 ? D ( G ) ? max { ? ( G ) + 2 , ( n + 5 ) / 2 } , where n denotes the number of vertices of G . In particular, D(G)?(n+5)/2 D ( G ) ? ( n + 5 ) / 2 for every G with no transposition in the automorphism group. If G is connected and has maximum degree d , we prove that D ( G ) ? c d n + O ( d 2 ) for a constant c d < 1 2 . A linear lower bound for graphs of maximum degree 3 with no transposition in the automorphism group follows from an earlier result by Cai, Frer, and Immerman [An optimal lower bound on the number of variables for graph identification, Combinatorica 12(4) (1992) 389410]. Our upper bounds for D(G) D ( G ) hold true even if we allow only definitions with at most one alternation in any sequence of nested quantifiers. In passing we establish an upper bound for a related number D(G,G?) D ( G , G ? ) , the minimum quantifier depth of a first order sentence which is true on exactly one of graphs G  and G? G ? . If G  and G? G ? are non-isomorphic and both have n  vertices, then D(G,G?)?(n+3)/2 D ( G , G ? ) ? ( n + 3 ) / 2 . This bound is tight up to an additive constant of 1. If we additionally require that a sentence distinguishing G  and G? G ? is existential, we prove only a slightly weaker bound D(G,G?)?(n+5)/2 D ( G , G ? ) ? ( n + 5 ) / 2 .
graph definability first order logic ehrenfeuct game