\left( n, p \right)$, then the sufficient conditions of Theorem \[th:suffCondErdRen\] and Theorem \[th:CheegerDirPart\] exhibit the same scaling behavior:

If the base-graph is drawn from the Erdős-Rényi model $ER \! \left( n, p \right)$, then it has a non-vanishing spectral gap for $p > C \log n / n$ (see [@jiang12]). Moreover, for every $\delta \in \left( 0,1 \right)$ and $p > 2 \log n / \left( \delta^2 n \right)$ [ ]{} 0 ( n ). Observe that if $\text{vol} \! \left( {\mathcal{S}}\right) > \left( 1 - \delta \right) p \, {\lvert{\mathcal{S}}\rvert} \left( n - 1 \right)$ for every ${\mathcal{S}}\subseteq V$, then $\min_{j} \text{deg} \! \left( v_j \right) \geq \left( 1 - \delta \right) \left( n - 1 \right) p$.

It is natural to give recovery guarantees in terms of the Cheeger constant: A graph with a small minimum cut consists of two rather disconnected components so that the probability of decoding one component without additive offset and the other component with constant additive offset $1$ is non-negligible. As we argue next, deriving a necessary condition that bounds the Cheeger constant away from zero is, however, impossible. Indeed, suppose the base-graph consists of two equally sized components, which are connected 