HLRB Project pr87mo

Eccentricities in Hanoi Graphs

Mathematisches Institut LMU

Eccentricities in Hanoi Graphs

Mathematisches Institut LMU

Mathematisches Institut LMU

Prof. Dr. Andreas Hinz

Theresienstraße 39

80333 München

The mathematical model of the well-known Tower of Hanoi game, with applications from psychology to computer science, are the Hanoi graphs Hn/p The p high n vertices represent the states of the game, i.e. the legal distributions of n discs among p pegs. A single move of one disc is modelled by an edge of the graph. While virtually everything is known for p = 3 and many topological graph parameters have been determined for all p, metric properties, referring to the distance between two vertices, i.e. the length of a shortest path leading from one to the other, are extremely hard to come by, even for the case p = 4, referring to The Reve's Puzzle. In 1941 B. M. Stewart and J. S. Frame came up with two algorithms and corresponding values for the length of the solution, the Frame-Stewart numbers, but a minimality proof was missing. The claim that their algorithms indeed lead to optimal move numbers is now known as the Frame-Stewart Conjecture (FSC) and open ever since. So far, its truth has been established by computer search for p = 4 and n <= 30 only. It came as a big surprise when R. Korf discovered during these computations that for n = 15 (but not for smaller n) the eccentricity of a perfect state, i.e. the largest distance from a regular state, and consequently the diameter of H; (this is the largest distance between any two states), is strictly larger than the distance between two perfect states, because everybody had expected that perfect states engender the worst case. Even more surprising was that this Korf phenomenon did not occur for n = 16 to 19, but reappeared for n = 20 to 22.The goal of this project is therefore to obtain a better understanding of the metric structure of Hanoi graphs H n/p by investigating the eccentricities of their vertices. E.g., the diameters of H are known for n <= 14 only. Moreover, Korf's phenomenon appears at n = 15, such that this case is a crucial threshold value for which we plan to calculate all eccentricities.

Impressum, Conny Wendler