Fiona Skerman: Tree automata on Galton-Watson trees

Abstract

This talk focuses on tree automata on Galton-Watson trees. A tree automaton $A$ is a finite set $\Sigma$ of colours, and a map $\Gamma: \mathbb{N}^{\Sigma} \rightarrow \Sigma$. Each root receives a colour as a function of the colours of its children. Under the Galton-Watson branching process set-up the probability that a node is coloured $\sigma$ is obtained as a fixed point of a system of equations. But this system need not have a unique fixed point.

The tree automaton colours locally; it assigns a colour to each node based on the colours of its child nodes. But can we colour each node $v$ looking only at the uncoloured structure rooted at $v$ in such a way that the resultant colouring `agrees' with the tree automaton at a fixed point? I shall formally define this global colouring, \emph{interpretation}, and provide a nearly complete description of necessary and sufficient conditions for a fixed point to \emph{not} admit an interpretation, in which case it is called \emph{rogue}. The inspiration for this work came from the branching process methods to study the 2-core of a random graph.   Joint work with Tobias Johnson and Moumanti Podder.