Zero-one laws for sentences with k variables

DOI10.1134/S1064562419030098MaRDI QIDQ2332084zbMATH OpenOpenAlexWikidataFDO

Authors M. E. Zhukovskii, A. Sarobidy Razafimahatratra

Publication date 1 November 2019

Published in Doklady Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s1064562419030098

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Random graphs (graph-theoretic aspects) (05C80)

Recommendations

• Zero-one laws for \(k\)-variable first-order logic of sparse random graphs
• When does the zero-one k-law fail?
• Zero-one laws for existential first-order sentences of bounded quantifier depth
• Universal zero-one k-law
• Ups and downs of first order sentences on random graphs

Cites work

• Bounded quantifier depth spectra for random graphs
• Elements of finite model theory.
• First-order properties of bounded quantifier depth of very sparse random graphs
• scientific article; zbMATH DE number 1072414 (Why is no real title available?)
• Infinitary logics and 0-1 laws
• Infinite spectra in the first order theory of graphs
• Logical laws for existential monadic second-order sentences with infinite first-order parts
• On infinite spectra of first-order properties of random graphs
• Probabilities on finite models
• Random graphs: models and asymptotic characteristics
• Small subgraphs and their extensions in a random distance graph
• Threshold spectra via the Ehrenfeucht game
• Zero-One Laws for Sparse Random Graphs

Cited in

(7)

• A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences
• \(\gamma\)-variable first-order logic of uniform attachment random graphs
• \( \gamma \)-variable first-order logic of preferential attachment random graphs
• Zero-one laws for \(k\)-variable first-order logic of sparse random graphs
• A geometric zero-one law
• EMSO(FO^2) 0-1 Law Fails for All Dense Random Graphs
• Ups and downs of first order sentences on random graphs

This page was built for publication: Zero-one laws for sentences with \(k\) variables

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