Failure of 0-1 law for sparse random graph in strong logics (Sh1062)

MaRDI QIDQ5221580zbMATH OpenFDO

Authors S. Shelah

Publication date 2 April 2020

Full work available at URL https://arxiv.org/abs/1706.01226

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Model theory of finite structures (03C13) Zero-one laws (60F20)

Abstract: Let $alphain(0,1{)}_{m}athbbR$ be irrational and $G_n=G_{{n,1/n}^{a}lpha}$ be the random graph with edge probability $1/n^{a}lpha$; we know that it satisfies the 0-1 law for first order logic. We deal with the failure of the 0-1 law for stronger logics: $mathbb{L}_{infty,k},k$ large enough and the LFP, least fix point logic.

Recommendations

• On failure of 0-1 laws
• Zero-one laws for \(k\)-variable first-order logic of sparse random graphs
• When does the zero-one k-law fail?
• scientific article; zbMATH DE number 1072414
• Ups and downs of first order sentences on random graphs

Cited in

(4)

• EMSO(FO$^2$) 0-1 Law Fails for All Dense Random Graphs
• The 0-1 law fails for monadic existential second-order logic on undirected graphs
• On failure of 0-1 laws
• Zero-one laws for \(k\)-variable first-order logic of sparse random graphs

This page was built for publication: Failure of 0-1 law for sparse random graph in strong logics (Sh1062)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5221580)