First-order definability of trees and sparse random graphs

Tom Bohman, Alan Frieze, Tomasz ŁUczak, Oleg Pikhurko, Clifford Smyth, Joel Spencer, Oleg Verbitsky

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)375-400
Number of pages26
JournalCombinatorics Probability and Computing
Issue number3
StatePublished - May 2007

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'First-order definability of trees and sparse random graphs'. Together they form a unique fingerprint.

Cite this