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 D(G) = ⊖(ln/ln ln n). where G is a random tree of order n or the giant component of a random graph script G sign(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.
ASJC Scopus subject areas
- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics