Zero-One Laws for Sentences with k Variables

摘要

The k-variable fragment of first-order logic on graphs is considered. It is proved that, for alpha <= 1/k - 1, the random graph G(n, n(-alpha)) obeys the zero-one law with respect to this logic. Moreover, for every epsilon > 0, there exists alpha is an element of (1/k - 1, 1/k - 1 +epsilon) such that G(n, n(-alpha)) does not obey the law.