2025/10/20 by Eppstein, David, Frishberg, Daniel, Maxwell, William
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2510.18010
The famous Tower of Hanoi puzzle involves moving n discs of distinct sizes from one of p≥ 3 pegs (traditionally p=3) to another of the pegs, subject to the constraints that only one disc may be moved at a time, and no disc can ever be placed on a disc smaller than itself. Much is known about the Hanoi graph Hpn, whose pn vertices represent the configurations of the puzzle, and whose edges represent the pairs of configurations separated by a single legal move. In a previous paper, the present authors presented nearly tight asymptotic bounds of O((p-2)n) and Ω(n(1-p)/2(p-2)n) on the treewidth of this graph for fixed p ≥ 3. In this paper we show that the upper bound is tight, by giving a matching lower bound of Ω((p-2)n) for the expansion of Hpn.