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 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 is the graph whose vertices are
the configurations of the puzzle on discs and 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 . 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 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)