2007-05-01Zeitschriftenartikel DOI: 10.18452/27701
First-Order Definability of Trees and Sparse Random Graphs
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 descriptive complexity of G in first-order logic. We show that almost surely , where G is a random tree of order n or the giant component of a random graph 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.
Files in this item
This publication is with permission of the rights owner freely accessible due to an Alliance licence and a national licence (funded by the DFG, German Research Foundation) respectively.