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


Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

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.

About the authors

A. N. Egorova

Moscow Institute of Physics and Technology (State University)

Author for correspondence.
Email: alena.egorova@phystech.edu
Russian Federation, Dolgoprudnyi, Moscow oblast, 141700

M. E. Zhukovskii

Moscow Institute of Physics and Technology (State University); Caucasus Mathematical Center, Adyghe State University

Author for correspondence.
Email: zhukmax@gmail.com
Russian Federation, Dolgoprudnyi, Moscow oblast, 141700; Maikop, Republic of Adygea, 385000

Supplementary files

Supplementary Files
Action
1. JATS XML

Copyright (c) 2019 Pleiades Publishing, Ltd.