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
| CREATOR | David Eppstein, Daniel Frishberg, William Maxwell |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-18010