Paper Info
Title
The first order definability of graphs: upper bounds for quantifier depth
Abstract
Let 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). We prove that σ(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 for every G with no transposition in the automorphism group. If G is connected and has maximum degree d, we prove that D(G) ≤ cdn + O(d2) for a constant cd 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'), the minimum quantifier depth of a first order sentence which is true on exactly one of graphs G and G'. If G and G' are non-isomorphic and both have n vertices, then D (G, G') ≤ (n + 3)/2. This bound is tight up to an additive constant of I. If we additionally require that a sentence distinguishing G and G' is existential, we prove only a slightly weaker bound D(G, G') ≤ (n + 5)/2.
Year
DOI
Venue
2006
10.1016/j.dam.2006.03.002
Discrete Applied Mathematics
Keywords
Field
DocType
ehrenfeuct game,n vertex,constant cd,order sentence,minimum quantifier depth,graph definability,order definability,related number,upper bound,first order logic,weaker bound d,graphs g,n denotes,graph g,maximum number,maximum degree,first order,directed graph
Adjacency list,Linear equation,Discrete mathematics,Combinatorics,Vertex (geometry),Bound graph,Upper and lower bounds,First order,Isomorphism,Degree (graph theory),Mathematics
Journal
Volume
Issue
ISSN
154
17
Discrete Applied Mathematics
Citations 
PageRank 
References 
8
0.72
16
Authors
3
Name
Order
Citations
PageRank
Oleg Pikhurko131847.03
Helmut Veith22476140.58
Oleg Verbitsky319127.50