Polynomial relaxation time on trees (Kenyon--Mossel--Peres)

Let $T_{b,k}$ be the rooted $b$-ary tree of depth $k$ ($b\ge2$, $k\ge1$): vertices are the words of length at most $k$ over a $b$-letter alphabet, each word joined to its $b$ one-letter extensions; write $n_k$ for its number of vertices. The Ising model on $T_{b,k}$ at inverse temperature $\beta>0$ is the distribution $\pi(\sigma)\propto\exp\bigl(\beta\sum_{\{v,w\}\in E}\sigma(v)\sigma(w)\bigr)$ on spin configurations, with Glauber dynamics re-sampling a uniformly chosen site from the conditional distribution. Among the eigenvalues of the dynamics (real $\lambda$ with $Pf=\lambda f$, $f\ne0$), let $\lambda_\star$ be the largest absolute value of an eigenvalue different from $1$; the relaxation time is $t_{\mathrm{rel}}=(1-\lambda_\star)^{-1}$, as in Mission VII.

The theorem (Theorem 15.6, Kenyon–Mossel–Peres; Levin–Peres–Wilmer) asserts the polynomial bound

On trees the relaxation time stays polynomial in the volume at every temperature — unlike the complete graph, where it becomes exponential below the critical temperature. The book's proof is an induction on depth powered by this mission's other tools: cutting the root's edges (the edge-removal proposition) splits the tree into independent subtrees whose product structure is handled by a block-dynamics comparison, at a per-level cost of $e^{2\beta(3b+1)}$ — which telescopes to the stated exponent.