On the expansion of Hanoi graphs

David Eppstein, Daniel Frishberg, William Maxwell · 2025

Read On the expansion of Hanoi graphs by David Eppstein, Daniel Frishberg, William Maxwell (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-18010.txt.

Description

David Eppstein, Daniel Frishberg, and William Maxwell finish a bound on the Tower of Hanoi graph by looking at how it expands. In the puzzle, disks move one at a time between pegs and never rest on a smaller disk. The graph's corners are legal setups, and its edges are single legal moves.

Earlier work by the same team pinned the graph's treewidth between two close bounds. Here they prove the upper bound is tight by giving a matching lower bound for expansion. Puzzle graphs may look playful, but the result is a firm statement about how such state spaces spread.

Catalog record

CREATORDavid Eppstein, Daniel Frishberg, William Maxwell
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-18010

Browse the full library · About the Tower of Babel