A logical approach to asymptotic combinatorics. II: Monadic second-order properties (Q2638642): Difference between revisions

The paper under review is a sequel of [the author, Adv. Math. 65, 65-96 (1987; Zbl 0646.60012)]. In that paper the author studied the problem of determining probabilities of first order properties holding in large finite structures randomly chosen from classes closed under disjoint unions and components. Now he considers, for the same classes, a general approach to problems about properties expressible in monadic second order logic. He defines an extended notion of asymptotic probability and gives sufficient conditions for the existence of extended asymptotic probabilities of monadic second-order sentences. Whenever the extended asymptotics of a monadic second order sentence is 0 or 1, then the sentence has an asymptotic probability (the same value). As a corollary one has that in rather general circumstances the asymptotic probability of connectivity in a random structure is 0. The author extends his earlier results to a characterization of non-fast, growing classes with monadic second-order 0-1 laws. Some sufficient conditions for the existence of asymptotic probabilities for all monadic second-order sentences are given.