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 probability , 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/pn+O(lglgn).