Colouring rules for finite trees

Alan Woods

(University of Western Australia)

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 sentences in monadic second order logic, about a rooted tree. It turns out that every such sentence has a well defined asymptotic probability. (In a slightly more general setting, this limit might, for example, be the probability that a "random" database organized as a rooted tree, has the property described by the sentence.)

A second situation to which the theory applies, is in finding the probability that a Boolean formula of size n in k variables computes a particular Boolean function, when n is large compared to k.

The methods used involve a smattering of logic, generating series, nonnegative matrices, and even (just a touch of) complex analysis.
Thursday 30th April 1998, 14:30
Seminar Room 322
Department of Computer Science