Decelle–Krzakala–Moore–Zdeborová conjecture for the planted partition model

For $n\to\infty$, let $\mathcal{G}(n,p,q)$ be the planted partition model with two uniformly random labels in $\{\pm1\}$, and let

$$p=\frac{a}{n},\qquad q=\frac{b}{n},$$

where $a$ and $b$ are fixed real numbers. A bisection is positively correlated with the original clusters if it agrees with their labels more often than chance.

Decelle–Krzakala–Moore–Zdeborová conjecture. If $(a-b)^2>2(a+b)$, one can almost surely find a bisection positively correlated with the original clusters; if $(a-b)^2<2(a+b)$, the reconstruction problem is not solvable. Moreover, there are no consistent estimators of $a$ and $b$ when $(a-b)^2<2(a+b)$, while consistent estimators exist whenever $(a-b)^2>2(a+b)$.

This conjecture describes the detectability threshold for the sparse two-community planted partition model. The source states that all three parts were subsequently proved: parts (ii) and (iii) by Mossel et al., and part (i) by Mossel et al. and Massoulié.