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

2019/07/08 by Moumanti Podder, Podder, Moumanti, Maksim Zhukovskii +1
Computer Science · Mathematics · #Algorithms and Data Compression #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1907.03879

openalex publication_date 2019/07/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For any fixed positive integer k, let α_k denote the smallest α∈ (0,1) such that the random graph sequence \G(n, n^-α)\ does not satisfy the zero-one law for the set E_k of all existential first order sentences that are of quantifier depth at most k. This paper finds upper and lower bounds on α_k, showing that as k → ∞, we have α_k = (k - 2 - t(k))^-1 for some function t(k) = Θ(k^-2). We also establish the precise value of α_k when k = 4.

Related

• Short monadic second order sentences about sparse random graphs
• First order sentences about random graphs: small number of alternations
• Universal Zero-One k--Law
• Upper bound for the minimal quantifier depth of the first part of a monadic second-order sentence without asymptotic probability
• Existential monadic second order logic of undirected graphs: a disproof of the Le Bars conjecture