Zero-one laws for existential first-order sentences of bounded quantifier depth

DOI10.1145/3489466MaRDI QIDQ5034234zbMATH OpenOpenAlexFDO

Authors Moumanti Podder, M. E. Zhukovskii

Publication date 24 February 2022

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

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

zbMATH Keywords

\( \alpha \)-safe pairsEhrenfeucht gamesexistential first-order logicgraph extension propertiesstrictly balanced graphszero-one laws

Mathematics Subject Classification ID

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

Abstract: For any fixed positive integer $k$, let $alph{a}_k$ denote the smallest $alphain(0,1)$ such that the random graph sequence $leftGleft(n,n^{-alpha}ight)ight$ does not satisfy the zero-one law for the set $mathcal{E}_k$ of all existential first order sentences that are of quantifier depth at most $k$. This paper finds upper and lower bounds on $alph{a}_k$, showing that as $kightarrowinfty$, we have $alph{a}_k=left(k-2-t(k)ight{)}^{-1}$ for some function $t(k)=Theta(k^{-2})$. We also establish the precise value of $alph{a}_k$ when $k=4$.

Recommendations

• First-order properties of bounded quantifier depth of very sparse random graphs
• When does the zero-one k-law fail?
• On the convergence of probabilities of the random graph properties expressed by first-order formulae with a bounded quantifier depth
• Bounded quantifier depth spectra for random graphs
• Universal zero-one k-law

Cited in

(9)

• Logical laws for existential monadic second-order sentences with infinite first-order parts
• Zero-one laws for sentences with \(k\) variables
• Bounded quantifier depth spectra for random graphs
• Zero-one law and definability of linear order
• First-order properties of bounded quantifier depth of very sparse random graphs
• On the convergence of probabilities of the random graph properties expressed by first-order formulae with a bounded quantifier depth
• Counterexamples of the 0-1 Law for Fragments of Existential Second-Order Logic: an Overview
• On first-order sentences without finite models
• Zero-one laws for first-order formulas with a bounded quantifier depth

This page was built for publication: Zero-one laws for existential first-order sentences of bounded quantifier depth

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