一句话：证明MSO在若干连通图类上满足零一律，去掉连通性后收敛律仍成立。
本文研究随机图上单调二阶逻辑（MSO）的极限定律，建立零一律与收敛律。作者考察若干具有结构限制的图类：连通平面图、树宽至多 k 的连通图，以及排除 k-团作为子式的连通图，证明 MSO（因而一阶逻辑）在这些类上满足零一律。进一步，若去掉连通性要求，相应的零一律不再成立，但 MSO 的收敛律仍然成立。结果揭示了平面性、有界树宽和禁子式等图类结构条件与 MSO 随机图逻辑行为之间的关系。
We establish zero-one laws and convergence laws for monadic second-order logic (MSO) (and, a fortiori, first-order logic) on a number of interesting graph classes. In particular, we show that MSO obeys a zero-one law on the class of connected planar graphs, the class of connected graphs of tree-width at most $k$ and the class of connected graphs excluding the $k$-clique as a minor. In each of these cases, dropping the connectivity requirement leads to a class where the zero-one law fails but a convergence law for MSO still holds.
@article{paperbot781,
title = {Logical properties of random graphs from small addable classes},
author = {Anuj Dawar and Eryk Kopczyński},
journal = {Logical Methods in Computer Science},
volume = {Volume 15, Issue 3},
year = {2019},
doi = {10.23638/lmcs-15(3:4)2019}
}