bound implies that $\text{vol} \! \left( {\mathcal{S}}\right) \leq \left( 1 + \delta \right) p \, {\lvert{\mathcal{S}}\rvert} \left( n - 1 \right)$ holds with high probability. Hence, instead of we could require that for some $\mu \in \left( 0,1 \right)$ and for every ${\mathcal{S}}\subseteq V$ with ${\lvert{\mathcal{S}}\rvert} \leq n - {\lvert{\mathcal{S}}\rvert}$

&gt; ( 1 - ) . \[eq:condCutVol\] Recalling that the Cheeger constant $h_G$ of a graph is $$\label{def:Cheegerconstant44}
h_G = \min_{{\mathcal{S}}\subseteq \left[n\right]} \frac{\text{cut} \! \left( {\mathcal{S}}\right)}{\min \! \left\{ \text{vol} \! \left( {\mathcal{S}}\right), \text{vol} \! \left( {\mathcal{S}}^c \right)\right\}},$$ it is clear that holds for every subset ${\mathcal{S}}\subseteq V$ if h\_G &gt; ( 1 - ) .

This motivates our next result, which is a recovery guarantee in terms of the Cheeger constant:

\[th:CheegerDirPart\]\[IT\_sufficient\_CheegerConstant\] If the base-graph $G = \left( V,E \right)$ has Cheeger constant $h_G$ and the minimum degree satisfies &gt; , \[eq:cheegSuffCond\] then exact recovery with high probability is possible. In particular, if the base-graph $G = \left( V,E \right)$ is $d$-regular, then a sufficient condition for exact recovery is &gt; . \[eq:cheegConstSuffCond\] If $\epsilon \rightarrow 1/2$, then is equivalent to &gt; + o ( ). \[eq:cheegSuffCond\_23\]

\
Interestingly, if the base-graph is drawn from the Erdős-Rényi model $\mathrm{ER} \! 