ICS 269, Spring 2022: Theory Seminar
Bren Hall 1423, 1:00 – 1:50

13 May 2022: Daniel Frishberg

On the treewidth and expansion of Hanoi graphs

The famous Tower of Hanoi puzzle consists of n discs of distinct sizes sitting on $p$ pegs. The discs begin on the first peg, and the object of the puzzle is to move all of the discs to the last peg, moving one disc at a time, while never placing a disc on another disc smaller than itself. The Hanoi graph $H(p,n)$ is the graph whose vertices are the configurations of the puzzle on $n$ discs and $p$ pegs, and whose edges are the pairs of configurations that differ by a single move. Previously in this seminar, the speaker presented the authors' previous work On the treewidth of Hanoi graphs, in which we gave lower and upper bounds for the treewidth of these graphs that were asymptotically nearly tight for fixed $p\ge 3$. In this presentation, we review these previous results and present a new result (in the process of being written) that tightens this asymptotic gap completely, up to a constant factor, when $p$ is fixed. We in fact do so by giving asymptotically tight bounds for the expansion of the same graphs.

(Joint work with David Eppstein and William Maxwell)