Zero­one laws for sentences with k variables

Abstract

We consider the k variable fragment of first order logic on graphs. We claim that, for $\alpha \le \frac{1}{\kappa -1}$, the random graph G(n, n^-α) obeys zero­one law w.r.t. this logic. Moreover, for every ε > 0 , there exists $\alpha \in \left(\frac{1}{\kappa -1},\frac{1}{\kappa -1}+\epsilon \right)$ such that G(n, n^-α) does not obey the law.