On the structure of random unlabelled acyclic graphs. (Q1426116)

The main result of this paper states that for every rooted tree \(T\) the asymptotic probability of choosing a tree having subtrees isomorphic to \(T\) is one (a tree \(A\) has the tree \(T\) with root \(r\) as subtree, if there is an embedding \(\pi\) of \(T\) in \(A\) such that \(A\setminus\pi(T\setminus r)\) is connected). As was shown by the author in a previous paper [ibid. 254, 331--347 (2002; Zbl 1011.03022)], this result implies that monadic second-order logic admits a zero-one law on trees.