The First Order Definability of Graphs: Upper Bounds for Quantifier Rank

Details The First Order Definability of Graphs: Upper Bounds for Quantifier Rank The First Order Definability of Graphs: Upper Bounds for Quantifier Rank

2003-11-04

arxiv.org/abs/math/0311041v1

Mathematics

Combinatorics

52 pages

Scientific paper

We say that a first order formula A distinguishes a graph G from another graph G' if A is true on G and false on G'. Provided G and G' are non-isomorphic, let D(G,G') denote the minimal quantifier rank of a such formula. We prove that, if G and G' have the same order n, then D(G,G')\le(n+3)/2, which is tight up to an additive constant of 1. The analogous questions are considered for directed graphs (more generally, for arbitrary structures with maximum relation arity 2) and for k-uniform hypergraphs. Also, we study defining formulas, where we require that A distinguishes G from any other non-isomorphic G'.

Affiliated with

Also associated with

No associations

Rating

The First Order Definability of Graphs: Upper Bounds for Quantifier Rank does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The First Order Definability of Graphs: Upper Bounds for Quantifier Rank, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The First Order Definability of Graphs: Upper Bounds for Quantifier Rank will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-265056