On the expansion of Hanoi graphs

The famous Tower of Hanoi puzzle involves moving $n$ discs of distinct sizes from one of $p\ge 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 $H_p^n$, whose $p^n$ 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 $\mathrm{\Omega }(n^{(1-p)\mathrm{/}2}(p-2{)}^n)$ on the treewidth of this graph for fixed $p\ge 3$. In this paper we show that the upper bound is tight, by giving a matching lower bound of $\mathrm{\Omega }((p-2{)}^n)$ for the expansion of $H_p^n$.