Dawar, Anuj and Kopczyński, Eryk - Logical properties of random graphs from small addable classes

lmcs:3780 - Logical Methods in Computer Science, July 25, 2019, Volume 15, Issue 3 - https://doi.org/10.23638/LMCS-15(3:4)2019
Logical properties of random graphs from small addable classes

Authors: Dawar, Anuj and Kopczyński, Eryk

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.


Volume: Volume 15, Issue 3
Published on: July 25, 2019
Submitted on: July 10, 2017
Keywords: Computer Science - Logic in Computer Science,Mathematics - Logic,03C13,F.4.1


Share

Consultation statistics

This page has been seen 159 times.
This article's PDF has been downloaded 92 times.