EMSO(FO${}^2$) 0-1 law fails for all dense random graphs

Abstract

In this paper, we disprove EMSO(FO${}^2$) convergence law for the binomial random graph $G(n,p)$ for any constant probability $p$. More specifically, we prove that there exists an existential monadic second order sentence with 2 first order variables such that, for every $p\in (0,1)$, the probability that it is true on $G(n,p)$ does not converge.