On the 4-spectrum of first-order properties of random graphs

DOI10.1134/S1064562421050185MaRDI QIDQ2116712zbMATH OpenOpenAlexFDO

Authors M. E. Zhukovskii, A. D. Matushkin, Yu. N. Yarovikov

Publication date 18 March 2022

Published in Doklady Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

first-order logiczero-one lawrandom binomial graphspectrum of formulaEhrenfeucht-Fraïssé game

Mathematics Subject Classification ID

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

Recommendations

• On infinite spectra of first-order properties of random graphs
• First order sentences about random graphs: small number of alternations
• On the spectra of first-order language properties for random graphs
• On limit points of spectra of first-order sentences with quantifier depth 4
• Quantifier alternation in first-order formulas with infinite spectra

Cites work

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• First order sentences about random graphs: small number of alternations
• Infinite spectra in the first order theory of graphs
• Monadic second-order properties of very sparse random graphs
• On infinite spectra of first-order properties of random graphs
• Probabilities on finite models
• The strange logic of random graphs
• Threshold spectra via the Ehrenfeucht game
• Zero-One Laws for Sparse Random Graphs
• Zero-one \(k\)-law

Cited in

(6)

• On infinite spectra of first-order properties of random graphs
• First order sentences about random graphs: small number of alternations
• On limit points of spectra of first-order sentences with quantifier depth 4
• Quantifier alternation in first-order formulas with infinite spectra
• On limit points of spectra of the random graph first-order properties
• Bounded quantifier depth spectra for random graphs

This page was built for publication: On the 4-spectrum of first-order properties of random graphs

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