First order sentences about random graphs: small number of alternations

DOI10.1016/j.dam.2017.10.017zbMath1377.05177arXiv1701.06517OpenAlexW2963793900MaRDI QIDQ1693159

A. D. Matushkin, M. E. Zhukovskii

Publication date: 11 January 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

first-order logicrandom graphszero-one lawsspectrum of first order sentences

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Strictly balanced uniform hypergraphs and generalizations of zero-one law, Disproof of the zero-one law for existential monadic properties of a sparse binomial random graph, Logical laws for short existential monadic second-order sentences about graphs, On limit points of spectra of first-order sentences with quantifier depth 4, A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences, Infinite spectra of first-order properties for random hypergraphs, On the 4-spectrum of first-order properties of random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Zero-one \(k\)-law
• First-order and monadic properties of highly sparse random graphs
• Threshold spectra via the Ehrenfeucht game
• Infinite spectra in the first order theory of graphs
• Threshold functions for extension statements
• Succinct definitions in the first order theory of graphs
• On infinite spectra of first-order properties of random graphs
• Zero-One Laws for Sparse Random Graphs
• Threshold functions for small subgraphs
• Estimation of the number of maximal extensions in a random graph
• Random graphs: models and asymptotic characteristics
• The strange logic of random graphs