The complexity of random ordered structures

Joel H. Spencer; K. St John

doi:10.1016/j.apal.2007.11.010

The complexity of random ordered structures

Joel H. Spencer, K. St John

Research output: Contribution to journal › Article › peer-review

Abstract

We show that for random bit strings, U_p (n), with probability, p = frac(1, 2), the first order quantifier depth D (U_p (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, G_p (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 (G_p (n)) = log_{1 / p} n + O (lg lg n).

Original language	English (US)
Pages (from-to)	174-179
Number of pages	6
Journal	Annals of Pure and Applied Logic
Volume	152
Issue number	1-3
DOIs	https://doi.org/10.1016/j.apal.2007.11.010
State	Published - Mar 2008

Keywords

Ehrenfeucht-Fraisse games
First order logic
Random graphs

ASJC Scopus subject areas

Logic

Access to Document

10.1016/j.apal.2007.11.010

Cite this

@article{188809b119b0495a8ebfbc685c2de571,

title = "The complexity of random ordered structures",

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).",

keywords = "Ehrenfeucht-Fraisse games, First order logic, Random graphs",

author = "Spencer, {Joel H.} and John, {K. St}",

note = "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{\`a}tica, Barcelona, Spain.",

year = "2008",

month = mar,

doi = "10.1016/j.apal.2007.11.010",

language = "English (US)",

volume = "152",

pages = "174--179",

journal = "Annals of Pure and Applied Logic",

issn = "0168-0072",

publisher = "Elsevier B.V.",

number = "1-3",

}

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 -

The complexity of random ordered structures

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this