vol. 28:2 2026 31 10.46298/dmtcs.16770 2025-10-23; None 2026-05-02

1 Introduction↩︎

1.1 Background and motivation↩︎

In the well-studied Tower of Hanoi puzzle, one is given \(n\) discs \(\{d_1, \dots, d_n\}\) of increasing size, sitting on the first of \(p\) pegs. The object is to move all of the discs to some specified peg, while moving one disc at a time, and without ever putting one disc \(d_i\) on a smaller disc \(d_j\), \(j < i\). The Hanoi graph \(H_p^n\) is the graph whose vertices correspond to the \(p^n\) possible configurations of the puzzle, and whose edges correspond to the pairs of configurations that differ by a single valid move.

Treewidth (see 2.2) is a graph connectivity property with broad applications in algorithm design and analysis (see e.g. [1]). Intuitively, treewidth measures how difficult it is to recursively decompose a graph via small vertex separators. The treewidth of large graphs having a natural combinatorial definitionsuch as Hanoi graphsis of independent theoretical interest. Some results are known e.g. for Kneser graphs [2] and their generalizations [3].

Expansion is a graph connectivity property that in some sense is stronger than treewidth; it measures the robustness of a graph with respect to “bottlenecks”, or sparse cuts. Expansion has a close connection to multicommodity flow problems via a kind of flow-cut duality. Prior work on the expansion of large graphs [4]–[6] connects closely to the study of the mixing properties of Markov chain Monte Carlo algorithms for counting and sampling problems [7], [8] (see also, e.g., [9]) via the relationship between (combinatorial) expansion and spectral expansion. Algorithmic questions involving expansion are also of interest (see e.g. [10]).

Certain graph properties of the special case \(p = 3\) of \(H_p^n\) have been somewhat easier to analyze than the case \(p \geq 4\). The Hanoi graph \(H_3^n\) on three pegs is known to have treewidth exactly four [11], and the diameter of \(H_3^n\) is \(2^n - 1\) [12]. On the other hand, for \(p \geq 4\), only (nearly tight) asymptotic bounds are known on the treewidth [11], and the diameter of \(H_p^n\) is unknown for \(p \geq 4\) [12] although values have been computed for small \(n\) when \(p = 4\), and compared with theoretical bounds [13].

1.2 Markov chain decomposition↩︎

Our technique builds on existing decomposition techniques developed in the analysis of Markov chain Monte Carlo (MCMC) algorithms for sampling problems. These algorithms are simple random walks that converge to a target distribution of interest. The mixing time of such an algorithmthe time it takes to converge to the target distributionis of interest, and often difficult to bound. A common means of obtaining such a bound is to use a standard theorem that relates the Cheeger constantessentially the expansion of the state space of the chain, viewed as a graph, up to normalization factorsto the mixing time.

In a prior work [5], motivated by the question of the mixing time of a well-studied [14], [15] chain for sampling polygon triangulations via a flip walk, the first and second author developed a framework for bounding the expansion of a graph by recursively decomposing the graph into subgraphs, and analyzing the mutual connectivity of the subgraphs at each level. Prior decomposition techniques existed in the MCMC setting, but these were too lossy to be of use for the triangulation flip walk. The triangulation flip walk has, as its state space, a well-studied graph known as the associahedron. Thus the problem of bounding the triangulation flip walk mixing time is equivalent to the problem of (lower-)bounding the expansion of the associahedron.

In a companion paper [16], the first and second authors further developed the framework and applied it to a number of other Markov chains.

1.3 Our contribution↩︎

In this paper, we apply the previous Markov chain decomposition framework to a large graph family that does not admit a natural Markov chain interpretation, showing that this framework is of independent interest beyond MCMC analysis. Furthermore, the family of graphs we are studyingHanoi graphsdo not admit a direct application of that framework, as written. We further develop the framework and show it can nonetheless be applied to Hanoi graphs.

The best known treewidth upper bound for \(H_p^n\) when \(p \geq 4\) is \(O((p-2)^n)\) [11]. Combining this known upper bound with a new lower bound, we prove the following:

In Section 2 we will define expansion and treewidth and observe a relationship between the two (2); from this relationship it will be immediate that if the expansion of a graph in a given family of bounded-degree graphs (such as Hanoi graphs) \(G = (V, E)\) is \(\Omega(f(|V|))\), then the treewidth of the same graph is \(|V|\cdot \Omega(f(|V|))\). From this relationship, Theorem [thm:hanoiexplb], and the upper bound on treewidth in [11] the following corollary is immediate (here \(|V| = p^n\)):

2 Preliminaries↩︎

2.1 Hanoi Graphs↩︎

By \(D = \{d_1, \dots, d_n\}\) we denote the set of \(n\) discs in the Tower of Hanoi puzzle such that whenever \(i > j\) the disc \(d_i\) is larger than the disc \(d_j\). By \([p] = \{1, \dots, p\}\) we denote the \(p\) pegs. A configuration in the Tower of Hanoi puzzle is given by a function mapping discs to pegs, i.e. \(\tau \colon D \rightarrow [p]\). Equivalently write \(\tau\) as a tuple, \(\tau = (\tau(d_1), \tau(d_2), \dots, \tau(d_n))\). Since no disc \(d_i\) can be placed on a smaller disc \(d_j\), each \(\tau\) indeed uniquely specifies a puzzle state. By \(H_p^n\) we denote the Hanoi graph associated with the Tower of Hanoi puzzle on \(n\) vertices and \(p\) pegs. The vertices of \(H_p^n\) are given by the configurations (the functions \(\tau \colon D \rightarrow [p]\)). There is an edge between two configurations \(\tau_1\) and \(\tau_2\) if and only if a player can transition from \(\tau_1\) to \(\tau_2\) by making exactly one legal move (that is, moving a disc from one peg to another, and placing it on top of a larger disc).

We define a decomposition of a Hanoi graph \(H_p^n\) into \(p\) induced Hanoi graphs isomorphic to \(H_p^{n-1}\) as in [11]. For a configuration \(\tau\) let \(\tau_n\) denote its \(n\)th component. That is, \(\tau_n\) denotes the peg on which the largest disc is placed in the configuration \(\tau\). For \(i=1,\dots,p\) the sets \(\{ \tau \mid \tau_n = i \}\) partition the vertices of \(H_p^n\) and the subgraphs induced by these sets are isomorphic to \(H_p^{n-1}\). See 1 for an illustration.

When referring to a Hanoi graph \(H \cong H_p^n\), we will denote by \(\{H_i\mid 1 \leq i \leq p\}\) the induced Hanoi subgraphs of \(H\) that are induced by the vertex sets \(\{\tau \mid \tau_n = i\}\). These subgraphs are mutually vertex-disjoint and are each isomorphic to \(H_p^{n-1}\). We call an edge in \(H^n_p\) a boundary edge if its endpoints lie in two distinct subgraphs \(H_i,H_j\), and we call a vertex a boundary vertex if it is incident to a boundary edge. Let \(\partial_e(H_i,H_j) = \{(u, v) \mid u \in H_i, v \in H_j, (u, v) \in E(H)\}\) be the set of boundary edges between a pair of subgraphs, and let \(\partial_v(H_i,H_j) = \{u \in H_i \mid \exists v \in H_j, (u, v) \in E(H)\}\) be the set of boundary vertices in \(H_i\) with a neighbor in \(H_j\).

We now analyze the structure of these subgraphs and the boundaries between them. First we define what we call a facet:

Under this definition, the restriction of a facet \(\mathcal{F}_{ij}(H)\) to a Hanoi subgraph \(H_k\) of \(H\) is itself a facet, namely \(\mathcal{F}_{ij}(H_k)\). Furthermore, by the symmetry among pegs, for all \(1 \leq k,l \leq p\) with \(k, l \notin \{i,j\}\), the restrictions \(\mathcal{F}_{ij}(H_k)\) and \(\mathcal{F}_{ij}(H_l)\) have the same cardinality. That is:

We now show that the boundary between each \(H_i\) and \(H_j\) induces a facet within each of \(H_i\) and \(H_j\):

We now have the following nice structure:

(Our previous paper [11] gives essentially the same proof of this fact.)

2.2 Expansion and treewidth↩︎

Our aim in this paper is to give asymptotically tight bounds on two key parameters for Hanoi graphs: expansion and treewidth. A graph with large expansion has no sparse cuts; a graph with large treewidth may have sparse cuts, but in a sense we will describe shortly, cannot be recursively decomposed via sparse cuts. Therefore, a lower bound on expansion induces a lower bound on treewidth, and an upper bound on treewidth induces an upper bound on expansion.

We now make these notions precise: given a graph \(G = (V, E)\), define the expansion, or edge expansion \(h(G)\) as \[h(G) = \min_{S \subseteq V: |S| \leq |V|/2}\{|\partial S|/|S|\}\] where \(\partial S = \{(u, v) \mid u \in S, v \in V \setminus S, (u, v) \in E\}\).

Define the vertex expansion \(h_v(G)\) as \[h_v(G) = \min_{S \subseteq V: |S| \leq |V|/2}\{|\partial_v S|/|S|\}\] where \(\partial_v S = \{v \in V \setminus S \mid \exists u \in S, (u, v) \in E\}\).

Unless specified as vertex expansion, we mean by “expansion” the edge expansion.

Treewidth, while closely related, is defined with respect to a tree decomposition: given \(G = (V, E)\), let a tree decomposition of \(G\), denoted \(\mathcal{T} = (\mathcal{X}, \mathcal{E})\) be a tree, whose nodes are a collection of bags (a term referring simply to subsets of \(V\)) \(\mathcal{X} = \{X_1, X_2, \dots, X_k\}\), satisfying the following conditions:

1. For all \(v \in V\), some bag \(X_i\) contains \(v\).

2. For all \((u, v) \in E\), some bag \(X_i\) contains \(u\) and \(v\).

3. For all \(v \in V,\) the set of bags containing \(v\) induces a nonempty (and connected) subtree of \(\mathcal{T}\).

Define the width of a tree decomposition \(\mathcal{T} = (\mathcal{X}, \mathcal{E})\) to be one less than the cardinality of the largest bag in \(\mathcal{X}\). Define the treewidth of a graph \(G\) to be the smallest possible width of a tree decomposition of \(G\). Denote the treewidth by \(\operatorname{tw}(G)\).

Define a balanced vertex separator \(X \subseteq V\) in a graph \(G = (V, E)\) as a set of vertices such that \(V \setminus X\) can be partitioned into two subsets \(A\) and \(B\) with \(|V|/3 \leq |A| \leq |B| \leq 2|V|/3\), where no vertex in \(A\) has a neighbor in \(B\).

2 immediately implies the following, by the definition of a balanced separator and of vertex expansion:

We observe the following consequence of the definitions of treewidth, expansion, and vertex expansion and of 2:

2.3 Expansion and multicommodity flows↩︎

Multicommodity flows are a standard tool for lower-bounding the expansion of a graph [6], [7]. Let \(G = (V, E)\) be a graph. Replace each (undirected) edge \(\{u, v)\} \in E\) by two directed edges \((u, v)\) and \((v, u)\). Denote the resulting set of directed edges by \(A\). A multicommodity flow \(f\) is a collection of functions \(\{f_{st}: A \rightarrow \mathbb{R}_{\geq 0} \mid (s, t) \in V \times V\}\) obeying the standard flow axioms:

1. \(\sum_{v \in N(s)} f_{st}(s, v) = \sum_{v \in N(t)} f_{st}(v, t) = 1\) ²

2. for all \(v \in V \setminus \{s, t\}\), \(\sum_{u \in N(v)} f_{st}(u, v) = \sum_{w \in N(v)} f_{st}(v, w)\)

By \(N(v)\) we mean \(\{u \in V: (u, v) \in E\}\).

Define the congestion of a multicommodity flow \(f\) as \(\frac{1}{|V|}\max_{(u, v) \in A}\sum_{(s, t) \in V \times V}f_{st}(u, v)\).

The following standard inequality relates multicommodity flows to expansion (see e.g. [7]):

3 Extending a prior framework↩︎

In two prior works [5], [16] the first and second author presented a framework consisting of a set of conditions that guarantee rapid mixing for the natural random walk on a family of graphs on \(N = f(n)\) vertices, where the family is parameterized by \(n << N\). This condition is equivalent to the graph having expansion \(\Omega\left(1/n^{O(1)}\right)\). They applied the framework to obtain rapid mixing results for random walks on the triangulations of a convex point set, as well as for a number of graph-theoretic sampling problems in bounded-treewidth graphs.

As we discussed in that paper, the framework is an analogue of the projection-restriction technique of Jerrum, Son, Tetali, and Vigoda [18]. The idea is to recursively partition the vertices of the graph into a small number of induced subgraphs in the same family, allowing a recursive decomposition. One can then construct a multicommodity flow recursively, by first specifying the amount of flow to send across each edge between a pair of the subgraphs, and then solving the resulting flow subproblems recursively.

The framework in [5] is as follows:

In fact, Eppstein and Frishberg [5] proved a stronger version of 4 that holds if the subgraphs in the decomposition are isomorphic to Cartesian products of smaller graphs in the family. However, these Cartesian products are not relevant to the case of Hanoi graphs.

In our case, the induced subgraphs are straightforward to find: in an \(H_p^n\) input graph, we define the subgraphs to be the \(p\) copies of \(H_p^{n-1}\) that correspond to playing the puzzle on the smallest \(n - 1\) discs given each of the \(p\) possible placements of the largest disc.

4 requires a strong lower bound (condition [addcondmatch]) on the number of edges between a given pair of the subgraphs, namely that the number of edges must be at least equal to the product of the cardinalities of the two subgraphs, divided by the total number of vertices in the graph. This condition fails for Hanoi graphs: this ratio is inverse exponential in \(n\). Nonetheless, we show how to repair the framework and apply it to Hanoi graphs. Informally, we use the fact that although the number of edges is much smaller than the stated bound, the boundary set between two subgraphsthe set of vertices in one subgraph \(H_p^{n-1}\) having neighbors in a given other subgraphis well distributed among the \(H_p^{n-2}\) subgraphs that comprise \(H_p^{n-1}\). We require also that each subgraph admits a decomposition into “facets” (2) allowing the construction of many “parallel” paths from such a boundary set to the other vertices within the subgraph. This avoids too much concentration of flow within a given vertex.

On the other hand, the decomposition of the Hanoi graph that we give here is simpler than those in [5]: that framework allowed each subgraph to be a Cartesian product of smaller graphs; here we have simply a smaller similar graphand that graph is in fact completely determined by its isomorphism to \(H_p^{n-1}\).

Thus the main contribution of this paper, in addition to establishing tight expansion and treewidth bounds for \(H_p^n\), is to give an extension of the framework where some of the conditions fail.

4 Large expansion for Hanoi graphs↩︎

In this section we adapt the framework of [5] to Hanoi graphs. We will prove the following:

Then Theorem [thm:hanoiexplb] will immediately follow via induction on \(n\) (with a trivial base case).

The construction in this section largely follows the construction used in [5] to prove 4. However, applying their construction breaks down in our case due to the small sets of edges between Hanoi subgraphs. We address this with the new machinery in 5.

The inductive structure comes from dividing \(H_p^n\) into \(p\) subgraphs as described in Section 3, each of which is isomorphic to \(H_p^{n-1}\). We then reuse the fractional paths given by the flow \(f\) for pairs of vertices lying in the same \(H_p^{n-1}\) copy. The rest of this section is devoted to routing flow between those pairs lying in different \(H_p^{n-1}\) copies.

Let \(H_1, \dots, H_p\) be the \(p\) copies of \(H_p^{n-1}\). Suppose a vertex \(s \in H_1\) wants to send an equal amount of flow to all vertices \(t \in H_2\). We first find some set of paths along which \(s\) sends its flow to the boundary vertices in \(H_1\)those having neighbors in \(H_2\)so that the flow is equally distributed among those boundary vertices. We let those boundary vertices simply send the flow across their edges to \(H_2\); then the boundary vertices in \(H_2\) need to find a way to distribute the flow to the rest of the vertices in \(H_2\).

We call this last step distribution; we call sending the flow across the boundary the transmission step; we will divide the first parthaving \(s\) send its flow to the boundaryinto two steps, one of which we call shuffling and one of which we call concentration. The shuffling step, which we will describe shortly, takes advantage of the inductive structure we described above.

Figure 2 shows the transmission and distribution steps in \(H_3^3\). (The distribution step is almost trivial in this case, since the boundary matching has size one.)

To formalize the division of this multicommodity flow into “steps,” we define the steps as a more general type of flow, as in [5]:

Given a graph \(G = (V, E)\), denote by \(A\) the set of directed arcs obtained by directing the edges of \(E\) in both directions as in the definition of a multicommodity flow in 2.3. Define a multi-way single-commodity flow (MSF) [5] as a function \(f: A \rightarrow \mathbb{R}_{\geq 0}\) with source set \(S \subseteq V\), sink set \(T \subseteq V\), and a set of surplus and demand amounts \(\sigma: S \rightarrow \mathbb{R}\) and \(\delta: T \rightarrow \mathbb{R}\), as a flow \(f: A \rightarrow \mathbb{R}\) in \(G\), such that:

1. for all \(s \in S \setminus T\) we have \(\sum_{v \in N(s)} (f(s, v) - f(v, s)) = \sigma(s)\)

2. for all \(t \in T \setminus S\) we have \(\sum_{v \in N(t)} (f(v, t) - f(t, v)) = \delta(t)\)

3. for all \(u \in S \cap T\) we have \(\sum_{v \in N(u)} (f(u, v) - f(v, u)) = \sigma(u) - \delta(u)\)

4. for all \(u \in V \setminus (S \cup T)\) we have \(\sum_{v \in N(u)}(f(u, v) - f(v, u)) = 0\)

Define by an MSF problem a tuple \(\pi = (S, T, \sigma, \delta)\),uio where \(S,T,\sigma,\delta\) are as described. Say that an MSF \(f\) solves the MSF problem \(\pi = (S, T, \sigma, \delta)\) if \(f\) is consistent with \(S,T,\sigma,\delta\).

In some cases \(\sigma\) or \(\delta\) will be a constant function, and in those cases we will abuse notation and write \(\sigma\) (resp. \(\delta\)) for the value \(\sigma(s)\) (resp. \(\delta(t)\)).

It follows from the definition of an MSF that, given MSFs \(f_1, f_2\) solving \(\pi_1 = (S_1, T_1, \sigma_1, \delta_1)\) and \(\pi_2 = (S_2 = T_1, T_2, \sigma_2 = \delta_1, \delta_2)\) one can compose the two MSFs \(f_1, f_2\)combine them into a third MSF \(f_2 \circ f_1\) that solves what we will call the composition \[\pi_2 \circ \pi_1 = (S_1, T_2, \sigma_1, \delta_2).\]

We can also take the sum of \(f_1\) and \(f_2\) to be \(f_3 = f_1 + f_2\), defined pointwise, so that \(f_3\) solves what we will call the sum of \(\pi_1\) and \(\pi_2\), i.e. \[\pi_1 + \pi_2 = (S_1 \cup S_2, T_1 \cup T_2, \sigma_3, \delta_3);\] for \(\sigma_3\) and \(\delta_3\) we naturally extend the domain to \(S_1 \cup S_2\): first, extend \(\sigma_1, \sigma_2, \delta_1, \delta_2\): for \(v \in S_2 \setminus S_1,\) let \(\sigma_1(v) = 0\); similarly for \(v \in S_1 \setminus S_2,\) let \(\sigma_2(v) = 0\). For \(v \in T_2 \setminus T_1\) let \(\delta_1(v) = 0\); similarly, for \(v \in T_1 \setminus T_1\) let \(\delta_2(v) = 0\).

Finally for all \(v\) let \(\sigma_3(v) = \sigma_1(v) + \sigma_2(v)\) and let \(\delta_3(v) = \delta_1(v) + \delta_2(v)\).

Now consider any two of the \(H_p^{n-1}\) subgraphs, without loss of generality \(H_1\) and \(H_2\). Consider the aggregate problem of letting each vertex \(s \in V(H_1)\) send a separate unit to every \(t \in V(H_2)\). We will decompose this problem into a collection of MSF subproblems, one for each source vertex \(s\). For each \(s\), call this subproblem

\[\pi_s = (\{s\}, V(H_2), \sigma_s = |V(H_2)|, \delta_s = 1).\]

Now we describe and formalize the shuffling step we have previously describedsimilar to the shuffling step in [5]as an MSF problem \(\pi_{shuf}\). We also define concentration, transmission, and distribution problems \(\pi_{conc}, \pi_{tran},\) and \(\pi_{dist}\).

The idea of the shuffling step \(\pi_{shuf}\) is, given a vertex \(s \in V(H_1)\) that needs to send flow to every \(t \in V(H_2)\), we let \(s\) first send an equal amount (a \(1/|V(H_1)|\) factor) of this flow to every \(s' \in V(H_1)\), using the flow \(f\) that exists in \(V(H_1)\) by the inductive hypothesis in Lemma [lem:hanoiindflow].

The idea of \(\pi_{conc}\), the concentration MSF, isafter we have uniformly distributed the outbound flow from \(s\) throughout \(V(H_1)\)to then concentrate this flow on the boundary \(\partial_v(H_1,H_2)\).

To send flow from \(\partial_v(H_1,H_2)\) across the edges \(\partial_e(H_1,H_2)\) between \(H_1\) and \(H_2\), we need to solve the transmission MSF, \(\pi_{tran}.\)

Finally, to ensure that all of the flow is distributed evenly throughout \(V(H_2)\) we need to solve the distribution step \(\pi_{dist}\).

5 states that to solve \(\pi_s\) it suffices to solve \(\pi_{shuf}, \pi_{conc}, \pi_{tran},\) and \(\pi_{dist}\).

We now show how to solve \(\pi_{shuf}\):

Next we solve \(\pi_{tran}\):

The hard part is to solve \(\pi_{conc}\) and \(\pi_{dist}\). Fortunately, however, these two MSFs are “mirror images” of one another: swapping the identities of \(H_1\) and \(H_2\), of sink and source vertices, and of \(\sigma\) and \(\delta\) functions is sufficient to transform one into the other. By this symmetry it suffices to solve \(\pi_{dist}\) and bound its congestion.

We do so in Section 5.

5 The distribution step↩︎

In this section we introduce new machinery that allows us to repair the framework in [5]. As we stated in 4, that framework breaks down for Hanoi graphs. In particular, Condition 3 of 4 fails, as the number of edges between a pair of Hanoi subgraphs is much smaller than needed for that condition.

Condition 3 requires that the number of edges between a pair of subgraphs be at least equal to the product of the cardinalities of the vertex sets of the subgraphs, divided by the total number of edges in the graph. This would give congestion at most one in the \(f_{tran}\) flow defined in 4.

However, since Condition 3 fails for Hanoi graphs, the \(f_{tran}\) flow has congestion (much) greater than one, causing an exponential blowup in the recursive construction that is needed to solve the \(\pi_{conc}\) and \(\pi_{dist}\) subproblems.

We address this problem by more carefully specifying the flow \(f_{dist}\) that solves the \(\pi_{dist}\) subproblem. To do so, we use the facets we defined in 2.

Recall that we defined \[\pi_{dist} = \left(\partial_v(H_2,H_1), V(H_2), \sigma_{dist} = \frac{|V(H_2)|}{|\partial_e(H_1,H_2)|}, \delta_{dist} = 1\right)\] as the problem of distributing \(|V(H_2)|\) units of flow, sent from some vertex \(s \in H_1\), equally throughout \(H_2\). Our goal is to construct \(f_{dist}\) so that it produces congestion at most \(\sigma_{dist}\). This will imply that the sum of \(|V(H_1)|\) such flowsone for each \(s \in V(H_1)\)produces at most \[|V(H_1)|\cdot\sigma_{dist} = |V(H_1)| \cdot \frac{|V(H_2)|}{|\partial_e(H_1,H_2)|} = (p/(p-2))^{n-2} \cdot |V(H_p^n)|\] units of flow across edges in \(H_2\), yielding \((p/(p-2))^{n-2}\) (normalized) congestion in the inductive step in Lemma [lem:hanoiindflow], as desired.

Define \(\{H_{1,i} \mid 1 \leq i \leq p\}\) as the \(p\) Hanoi subgraphs of \(H_1\). Define \(\{H_{2,i}\}\) similarly. We construct \(f_{dist}\) recursively by decomposing \(\pi_{dist}\) into MSF subproblems:

We briefly describe each of the problems defined in 8. (Figure 3, Figure 4, and Figure 5 visualize these problems for the case \(p = 4\).) Our task in constructing \(f_{dist}\) is to distribute flow from the boundary set \(\partial_v(H_2,H_1)\) in \(H_2\) throughout the rest of \(H_2\). Consider that \[\partial_v(H_2,H_1)~=~\mathcal{F}_{12}(H_2)~=~\bigcup_{i=3}^p\mathcal{F}_{12}(H_{2i}) = \bigcup_{i=3}^p\left(\partial_v(H_2,H_1) \cap V(H_{2,i})\right)\] is both itself a facet, and also a union of facets within Hanoi subgraphs of \(H_2\). Thus \(\pi_{distsub,i}\) is the problem of distributing the flow received from \(s \in H_1\) evenly throughout the \(i\)th subgraph \(V(H_{2,i})\).

For \(3 \leq i \leq p\), \(H_{2,i} \cap \partial_v(H_2,H_1) = \mathcal{F}_{12}(H_{2,i}) \neq \emptyset\); therefore \(H_{2,i}\) receives flow from \(H_1\) directly. This flow must be distributed evenly throughout \(H_{2,i}\); this is accomplished by solving \(\pi_{distsub,i}\).

However, \(V(H_{2,1})\) and \(V(H_{2,2})\) do not contain boundary vertices, i.e. \(V(H_{2,1}) \cap \partial_v(H_2,H_1) = \emptyset\) and \(V(H_{2,2}) \cap \partial_v(H_2,H_1) = \emptyset\). Therefore, we must route flow from the other \(H_{2,i}\) (\(3 \leq i \leq p\)) subgraphs to \(V(H_{2,1})\) and \(V(H_{2,2})\) before solving \(\pi_{distsub,1}\) and \(\pi_{distsub,2}\). The problem of doing so is to solve \(\pi_{tran,i,1}\) and \(\pi_{rout,i,1}\) (\(1 \leq 3 \leq p\)).

More precisely, \(\pi_{tran,ij}\) is the problem of transmitting enough flow across the boundary \(\partial_e(H_{2i},H_{2j})\) to ensure that all of the \(p\) subgraphs of \(H_2\) end up with the same total amount of flow. This is solved by defining a flow \(f_{tran,ij}\) that simply sends the flow across each edge in the boundary matching \(\partial_e(H_{2i},H_{2j})\).

The problems \(\pi_{rout,i,1}\) and \(\pi_{rout,i,2}\) are induced by \(f_{tran,ij}, j \in \{1,2\}\): \(f_{tran,ij}\) transmits flow evenly among \(H_p^{n-2}\) copies in \(H_2\), and \(f_{distsub,i}\) (once we construct it) will distribute flow evenly within each subgraph. The problem \(\pi_{rout,i,1}\) (respectively \(\pi_{rout,i,2}\)) is that of routing, through \(H_{2,i}\), for \(3 \leq i \leq p\), the flow from \(H_1\) that is bound for \(H_{2,1}\) (respectively \(H_{2,2}\)).

We now prove 8:

We now have a complete recursive decomposition of \(\pi_{dist}\)originally defined within \(H_2 \cong H_p^{n-1}\)into subproblems on its \(H_p^{n-2}\) subgraphs.

(The base case occurs when \(n = 2\), and \(H_p^{n-1}\) is a clique.)

This decomposition, pending the definition of \(f_{tran,ij}\), yields a recursive definition of \(f_{dist}\).

We now bound the resulting congestion:

We can now prove Lemma [lem:hanoiindflow]:

Theorem [thm:hanoiexplb] follows via induction on \(n\).

References↩︎

---

1. Research of David Eppstein was supported in part by NSF grant CCF-2212129.↩︎

2. In this paper we only consider uniform multicommodity flows, in which the right-hand side of the equality in the first condition is \(1\).↩︎