Disproof of the Zero–One Law for Existential Monadic Properties of a Sparse Binomial Random Graph

Resumo

Existential monadic second-order sentences are constructed that have no limit probabilities on the sparse binomial random graph \(G(n,{{n}^{{ - \alpha }}})\). For \(\alpha < \frac{1}{2}\), the constructions have only one monadic variable.