Existential monadic second order logic of undirected graphs: the Le Bars conjecture is false (Q1715478)

The authors construct a sentence \(\varphi\) in existential monadic second-order logic (EMSO) with two monadic variables and first-order quantifier depth 2 and with the following property. The probability that a random (labelled undirected) graph with vertex set \(\{1, \ldots, n\}\) satisfies \(\varphi\) does not converge as \(n \to \infty\). The probability distribution used is the uniform one, or equivalently, every edge has probability \(1/2\) independently of other edges. This result refines earlier non-convergence results for monadic second-order logic. Then it is proved that there is a dense set \(D \subseteq (0, 1)\) such that, for every \(p \in D\), a similar non-convergence result holds for EMSO and for graphs where each edge has probability \(p\) independently of other edges. The first result disproves a conjecture of [\textit{J.-M. Le Bars}, Inf. Process. Lett. 77, No. 1, 43--48 (2001; Zbl 1003.03035)].