TY - JOUR

T1 - The complexity of random ordered structures

AU - Spencer, Joel H.

AU - John, K. St

N1 - Funding Information:
The second author gratefully acknowledges support from NSF ITR 01-21651 and MRI 02-15942 and the hospitality of the Centre de Recerca Matemàtica, Barcelona, Spain.

PY - 2008/3

Y1 - 2008/3

N2 - 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).

AB - 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).

KW - Ehrenfeucht-Fraisse games

KW - First order logic

KW - Random graphs

UR - http://www.scopus.com/inward/record.url?scp=39649122111&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=39649122111&partnerID=8YFLogxK

U2 - 10.1016/j.apal.2007.11.010

DO - 10.1016/j.apal.2007.11.010

M3 - Article

AN - SCOPUS:39649122111

SN - 0168-0072

VL - 152

SP - 174

EP - 179

JO - Annals of Pure and Applied Logic

JF - Annals of Pure and Applied Logic

IS - 1-3

ER -