Hanoi Towers, Schreier Graphs, Iterated Monodromy Groups and Julia sets
by
Zoran Sunik
Texas A&M University
Coauthors: Rostislav Grigorchuk

We model the well known Hanoi Towers Problem on k pegs by a self-similar group H(k) acting on a k-regular rooted tree. The Schreier graph of the action of the group H(k) on level n in the tree models the n-disk version of the problem. As n goes to infinity the obtained limiting graph is the Schreier graph of the action of H(k) on the boundary of the k-ary tree.

For the original version of Hanoi Towers on 3 pegs the obtained group H(3) is an automaton group branching regularly over its commutator. The corresponding finite Schreier graphs are 3-regular graphs that approximate the Sierpinski gasket. The group H(3) can be described as the iterated monodromy group of a post-critically finite map f on the Riemann sphere. The Julia set of the map f is homeomorphic to the limiting infinite Schreier graph.

The action of H(3) on the levels of the tree provides permutational representations that can be used to determine the spectrum of the Markov operator on the associated Schreier graphs. The spectrum can be described as the closure of the backward orbit of a quadratic polynomial p. It consists of a countable set of isolated points that accumulate to a Cantor set, which is the Julia set of the polynomial p.

Paper reference: arXiv:math.GR/0601592

Date received: February 9, 2006