Abstract

Let φ be a monadic second order sentence about a finite structure from a class K which is closed under disjoint unions and has components. Compton has conjectured that if the number of n element structures has appropriate asymptotics, then unlabelled (labelled) asymptotic probabilities ν(φ) (μ(φ) respectively) for φ always exist. By applying generating series methods to count finite models, and a tailor made Tauberian lemma, this conjecture is proved under a mild additional condition on the asymptotics of the number of single component K-structures. Prominent among examples covered, are structures consisting of a single unary function (or partial function) and a fixed number of unary predicates