The 0-1 law fails for monadic existential second-order logic on undirected graphs
Our purpose is to draw the frontier line which separates logics with and without 0-1 laws for the fragments of monadic existential second-order logic (MESO for short). We establish the failure of the 0-1 law for monadic existential second-order logic on undirected graphs by giving a sentence in this logic which has no asymptotic probability This improves a similar result by Kaufmann on a vocabulary of 4 directed binary relations. Both results require 9 first-order variables. In contrast, we conjecture that the el law holds for MESO with two first-order variables (that is MESO2) on undirected graphs. Our result is optimal with respect to the vocabulary. The report is self-contained (C) 2001 Elsevier Science B.V. All rights reserved.
logics theory of computation combinatorial problems