Texas A&M University, Department of
Mathematics, 216 Milner Hall, 14th of September 2005, 3:00-3:50
Groups and Dynamics Seminar
Hanoi Towers and
self-similar groups
Zoran Šunić of Texas A&M University
We will show how the well known Hanoi Towers Problem can be modeled by
a regularly branched group defined by a bounded finite automaton. The
recursive nature of the problem is reflected in the self-similarity
structure of the obtained group. The configuration space for a fixed
number of disks n can be represented as a Schreier graph of the
automaton group at level n. The obtained graphs are known as Sierpinski
graphs.
Many versions of the original problem (for any number of pegs and with
various restrictions on the possible moves) can also be modeled by
automaton groups. In most cases, the actual diameter of the obtained
graphs (telling us what is the minimal number of moves to solve the
corresponding variation of the puzzle) is not known.