Decelle et al.'s partial-recovery threshold conjecture for the stochastic block model

Throughout, let $G(n,a/n,b/n)$ be the two-community stochastic block model with two roughly equal-sized communities, within-community connection probability $a/n$, between-community connection probability $b/n$, sparse parameters $a,b=\Theta(1)$, and $a>b$. Decelle et al.'s threshold conjecture. If

$$(a-b)^2>2(a+b),$$

then partial recovery in $G(n,a/n,b/n)$ is possible, whereas if

$$(a-b)^2<2(a+b),$$

then partial recovery is information-theoretically impossible. The conjecture identifies the Kesten–Stigum threshold for partial recovery in the sparse symmetric two-community model; the source states that these conjectures have since been resolved.