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

zbMATH Open1433.03072arXiv1706.01226MaRDI QIDQ5221580FDOQ5221580

Authors: S. Shelah 

Publication date: 2 April 2020

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.

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

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

Mathematics Subject Classification ID

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

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)