Anuj Dawar ; Eryk Kopczyński - 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 classesArticle

Authors: Anuj Dawar ; Eryk Kopczyński

    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
    Accepted on: June 7, 2019
    Submitted on: July 10, 2017
    Keywords: Computer Science - Logic in Computer Science,Mathematics - Logic,03C13,F.4.1

    Consultation statistics

    This page has been seen 1605 times.
    This article's PDF has been downloaded 261 times.