First Order Definability of Trees and Sparse Random Graphs

Details First Order Definability of Trees and Sparse Random Graphs First Order Definability of Trees and Sparse Random Graphs

2005-06-15

arxiv.org/abs/math/0506288v1

Mathematics

Combinatorics

28 pages

Scientific paper

Let D(G) be the smallest quantifier depth of a first order formula which is true for a graph G but false for any other non-isomorphic graph. This can be viewed as a measure for the first order descriptive complexity of G. We will show that almost surely D(G)=\Theta(\ln n/\ln\ln n), where G is a random tree of order n or the giant component of a random graph G(n,c/n) with constant c>1. These results rely on computing the maximum of D(T) for a tree T of order n and maximum degree l, so we study this problem as well.

Affiliated with

Also associated with

No associations

Rating

First Order Definability of Trees and Sparse Random Graphs 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 First Order Definability of Trees and Sparse Random Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and First Order Definability of Trees and Sparse Random Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-288780