to be recoverable from the edge-variables $Y^E$ except with some probability that vanishes as the number of vertices increases.

\[th:suffCondErdRen\]\[IT\_sufficient\_ErdosReinyi\] Suppose the base-graph is drawn from the Erdős-Rényi model $ER \! \left( n, p \right)$ with $p > 2 \log n / n$, and let $d$ denote its expected average degree, i.e., $d = (n-1)p$. Then the condition + o ( ) \[eq:suffCondRandGraphThm\] is sufficient to guarantee exact recovery with high probability. If $\epsilon \rightarrow 1/2$, the condition is + o ( ). \[eq:suffCondErdRenBigEps\]

\
In the proof of Theorem \[th:suffCondErdRen\], we used the fact that, for a graph from the Erdős-Rényi model $ER \! \left( n, p \right)$, the cut of each subset ${\mathcal{S}}\subseteq V$ is with high probability approximately as large as its expectation, i.e., for $\delta > 0$ it holds with high probability that ( ) &gt; ( 1 - ) p ( n - ), V. \[eq:motForCheeger\] For every set ${\mathcal{S}}\subseteq V$, define ( ) = \_[v ]{} ( v ). Note that ${{\mathbb{E}}\! \left[\text{vol} \! \left( {\mathcal{S}}\right)\right]} = p \, {\lvert{\mathcal{S}}\rvert} \left( n - 1 \right)$ and ${{\mathbb{E}}\! \left[\text{cut} \! \left( {\mathcal{S}}\right)\right]} = p \, {\lvert{\mathcal{S}}\rvert} \left( n - {\lvert{\mathcal{S}}\rvert} \right)$. Moreover, the multiplicative Chernoff 