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

A. N. Egorova^a^,* and M. E. Zhukovskii^a^,^b^,**
Translated by I. Ruzanova

^aMoscow Institute of Physics and Technology (State University), Dolgoprudnyi, Moscow oblast, 141700 Russia

^bCaucasus Mathematical Center, Adyghe State University, Maikop, 385000 Republic of Adygea, Russia

Correspondence to: *e-mail: alena.egorova@phystech.edu
Correspondence to: **e-mail: zhukmax@gmail.com

Received 13 September, 2018

Abstract—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.

DOI: 10.1134/S1064562419010216