$b\in \left\lbrace 1,2,\ldots,2^{n}\right\rbrace$) and shows that $$\Gamma_n^\star = \tfrac{1}{3}\left(1-\tfrac{h}{J}+\left\lceil \tfrac{h}{J}\right\rceil \right)
\left(2^{\left\lceil n-\tfrac{h}{J}\right\rceil }-4+2\epsilon\right)-\epsilon, \qquad
K_n^\star = \frac{\left\lceil \tfrac{h}{J}\right\rceil !}{n!\,2^{n-4}\left(3-\epsilon\right)},$$ with $\epsilon=\left\lceil n-h\right\rceil \mbox{mod }2$. Hypothesis (H) has been verified.

### Complete graph

For Glauber dynamics on the complete graph $K_n$, it is easy to see that any monotone path from $\boxminus$ to $\boxplus$ is an optimal path. It is straightforward to show that ${\mathcal{C}}^\star=\{U\subseteq V\colon\,|U|=n^\star\}$ with $n^\star = \lceil\frac{1}{2}
(n-1-\tfrac{h}{J})\rceil$, whenever $\frac{h}{J}$ is not an integer, and to compute $$\label{GKexp}
\Gamma_n^\star=n^\star(J(n-n^\star)-h), \qquad  K_n^\star=\frac{1}{|{\mathcal{C}}^\star|}
\frac{n}{n-n^\star}.$$ Metastable behaviour occurs for any value of $h$ and $J$, provided $n$ is large enough. Hypothesis (H) is also easy to confirm by observing that every configuration lies on some optimal path. Like the hypercube, $K_n$ is an expander graph and consequently the communication height $\Gamma^\star$ grows at least linearly with the number of vertices (quadratically for $K_n$).

We can reduce the quadratic growth by introducing an interaction parameter that is inversely proportional to the size of the graph: e.g. $J=\tfrac{J'}{n}$ for some constant $J'>0$, with $h>0$ fixed. It follows that $$\Gamma_{n}^\star=n^\star\left(J'\left(\frac{n-n^\star}{n}-h\right)\right),$$ where this time $n^\star=\lceil\frac{n}{2}(1-\tfrac{h}{J'})-\frac{1}{2}\rceil$, and $K_n^\star$ is the same as in . Metastable behaviour occurs if and only if $\tfrac{h}{J'}
<1-\frac{1}{n}$.

### Erdős-Rényi 