Existential monadic second order convergence law fails on sparse random graphs

Alena Egorova, Maksim Zhukovskii

In the paper, we prove that existential monadic second order convergence law fails for the binomial random graph $G(n,n^{-\alpha })$ for every $\alpha \in (0,1)$.