Zero-One Laws for Existential First-Order Sentences of Bounded Quantifier Depth

Abstract

For any fixed positive integer k, let αk denote the smallest α ∈ (0,1) such that the random graph sequence {G(n, n-α)}n does not satisfy the zero-one law for the set εk of all existential first-order sentences that are of quantifier depth at most k. This article 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.