We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
First-Order Definability of Trees and Sparse Random Graphs.
- Authors
BOHMAN, TOM; FRIEZE, ALAN; ŁUCZAK, TOMASZ; PIKHURKO, OLEG; SMYTH, CLIFFORD; SPENCER, JOEL; VERBITSKY, OLEG
- 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)=\Theta(\frac{\ln n}{\ln\ln n})$, where G is a random tree of order n or the giant component of a random graph $\C G(n,\frac cn)$ 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.
- Subjects
TREE graphs; RANDOM graphs; MATHEMATICAL formulas; MEASURE theory; ISOMORPHISM (Mathematics); FIRST-order logic; MAXIMA &; minima; TOPOLOGICAL degree
- Publication
Combinatorics, Probability & Computing, 2007, Vol 16, Issue 3, p375
- ISSN
0963-5483
- Publication type
Article
- DOI
10.1017/S0963548306008376