Alan Woods, Dept. of Mathematics, Uni. of Western Australia

The asymptotics of colouring rules for finite trees

Consider a set of rules for colouring the vertices of any finite rooted tree with a fixed finite number of colours, starting at the leaves and working towards the root. Assume that the colour assigned to each vertex depends only on how many of its immediate predecessors (in the process) there are of each colour. What can be said about the fraction of $n$ vertex trees with a given root colour? This situation arises when considering properties of a rooted tree expressable in monadic second order logic ---it turns out that every such property has a well defined asymptotic probability--- and also in the study of Boolean formulas.