24 October 2013

11:00

Marc Noy

Abstract

<p>Let $G$ be an addable minor-closed class of graphs. We prove that a zero-one
law holds in monadic second-order logic (MSO) for connected graphs in G,
and a convergence law in MSO for all graphs in $G$. For each surface $S$, we
prove the existence of a zero-one law in first order logic (FO) for
connected graphs embeddable in $S$, and a convergence law in FO for all
graphs embeddable in $S$. Moreover, the limiting probability that a given FO
sentence is satisfied is independent of the surface $S$. If $G$ is an addable
minor-closed class, we prove that the closure of the set of limiting
probabilities is a finite union of intervals, and it is the same for FO
and MSO. For the class of planar graphs it consists of exactly 108
intervals. We give examples of non-addable classes where the results are
quite different: for instance, the zero-one law does not hold for
caterpillars, even in FO.
This is joint work with Peter Heinig, Tobias Müller and Anusch Taraz.
</p>