Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 375-400 |
Number of pages | 26 |
Journal | Combinatorics Probability and Computing |
Volume | 16 |
Issue number | 3 |
DOIs | |
State | Published - May 2007 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics