Open AccessA disproof of the zero-one law for existential monadic second order properties of sparse binomial random graphs
Author(s) -
Alena Egorova,
Alena Egorova,
Maksim Zhukovskii,
Maksim Zhukovskii
Publication year - 2019
Publication title -
doklady akademii nauk. rossijskaâ akademiâ nauk
Language(s) - English
Resource type - Journals
ISSN - 0869-5652
DOI - 10.31857/s0869-56524845519-522
Subject(s) - mathematics , limit (mathematics) , binomial (polynomial) , zero (linguistics) , binomial coefficient , combinatorics , graph , order (exchange) , random graph , random variable , existentialism , discrete mathematics , binomial theorem , law , statistics , philosophy , linguistics , mathematical analysis , finance , political science , economics
We construct existential monadic second order sentences that have no limit probabilities on binomial sparse random graph G(n; n–α) . For α < , the constructions have only one monadic variable.