The complexity of random ordered structures

Joel H. Spencer, K. St John

Research output: Contribution to journalArticlepeer-review

Abstract

We show that for random bit strings, Up (n), with probability, p = frac(1, 2), the first order quantifier depth D (Up (n)) needed to distinguish non-isomorphic structures is Θ (lg lg n), with high probability. Further, we show that, with high probability, for random ordered graphs, G≤, p (n) with edge probability p = frac(1, 2), D (G≤, p (n)) = Θ (log* n), contrasting with the results for random (non-ordered) graphs, Gp (n), given by Kim et al. [J.H. Kim, O. Pikhurko, J. Spencer, O. Verbitsky, How complex are random graphs in first order logic? Random Structures and Algorithms 26 (2005) 119-145] of D (Gp (n)) = log1 / p n + O (lg lg n).

Original languageEnglish (US)
Pages (from-to)174-179
Number of pages6
JournalAnnals of Pure and Applied Logic
Volume152
Issue number1-3
DOIs
StatePublished - Mar 2008

Keywords

  • Ehrenfeucht-Fraisse games
  • First order logic
  • Random graphs

ASJC Scopus subject areas

  • Logic

Fingerprint Dive into the research topics of 'The complexity of random ordered structures'. Together they form a unique fingerprint.

Cite this