Existential monadic second order logic of undirected graphs: The Le Bars conjecture is false |
| |
Authors: | S.N. Popova M.E. Zhukovskii |
| |
Affiliation: | 1. Moscow Institute of Physics and Technology, Laboratory of Advanced Combinatorics and Network Applications, Russian Federation;2. The Russian Presidential Academy of National Economy and Public Administration, Russian Federation |
| |
Abstract: | In 2001, J.-M. Le Bars disproved the zero-one law (that says that every sentence from a certain logic is either true asymptotically almost surely (a.a.s.), or false a.a.s.) for existential monadic second order sentences (EMSO) on undirected graphs. He proved that there exists an EMSO sentence ? such that does not converge as (here, the probability distribution is uniform over the set of all graphs on the labeled set of vertices ). In the same paper, he conjectured that, for EMSO sentences with 2 first order variables, the zero-one law holds. In this paper, we disprove this conjecture. |
| |
Keywords: | 03C85 03C13 60C05 05C80 Zero-one law Binomial random graph Existential monadic second order logic Le Bars conjecture |
本文献已被 ScienceDirect 等数据库收录! |
|