Zero-one laws for k-variable first-order logic of sparse random graphs

Abstract

In this paper, we prove that for every positive $\epsilon$, there exists an $\alpha \in (1/(k-1),1/(k-1)+\epsilon )$ such that the binomial random graph $G(n,n^{-\alpha })$ does not obey 0-1 law w.r.t. first order sentences with k variables. In contrast, for every $\alpha \in (0,1/(k-1)]$, $G(n,n^{-\alpha })$ obeys 0-1 law w.r.t. this logic.

References in corpus (1)

• Failure of 0-1 law for sparse random graph in strong logics