The Complexity of Random Ordered Structures

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