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

DOI10.1134/S1064562421050185zbMath1484.05191OpenAlexW4210385964MaRDI QIDQ2116712

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 logicEhrenfeucht-Fraïssé gamezero-one lawrandom binomial graphspectrum of formula

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Zero-one \(k\)-law
• Threshold spectra via the Ehrenfeucht game
• Infinite spectra in the first order theory of graphs
• First order sentences about random graphs: small number of alternations
• Monadic second-order properties of very sparse random graphs
• On infinite spectra of first-order properties of random graphs
• Zero-One Laws for Sparse Random Graphs
• Probabilities on finite models
• The strange logic of random graphs

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