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 journalArticle

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

ASJC Scopus subject areas

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

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

  • Cite this

    Bohman, T., Frieze, A., ŁUczak, T., Pikhurko, O., Smyth, C., Spencer, J., & Verbitsky, O. (2007). First-order definability of trees and sparse random graphs. Combinatorics Probability and Computing, 16(3), 375-400. https://doi.org/10.1017/S0963548306008376