Exact three- and four-state reconstruction thresholds and four-state tree capacity

We establish the exact Kesten–Stigum reconstruction threshold for the ferromagnetic four-state Potts broadcast model on every regular d-ary tree with d ≥ 2 and every Poisson Galton–Watson tree of mean d > 0. Reconstruction occurs exactly when \(d\lambda^2\gt 1\); we prove nonreconstruction at and below the threshold, including equality. In the Poisson model the whole tree is observed and the reconstruction advantage is averaged without conditioning on survival. The proof uses reproducible exact-arithmetic verification of polynomial inequalities.

For the ferromagnetic four-state broadcast model with \(0\lt \lambda\lt 1\), we prove that reconstruction on a bounded-degree deterministic rooted tree occurs exactly when its L³ capacity with edge resistances \(\lambda^{-2|e|}\) is positive. This gives an exact criterion without regularity or growth-rate assumptions on the tree, including at the exponential critical boundary.

We determine the exact reconstruction threshold for the symmetric three-state broadcast process on every regular b-ary tree, b ≥ 2, and every observed Poisson Galton–Watson tree of mean d > 1. Reconstruction occurs exactly when \(d\lambda^2\gt 1\), with d = b in the regular model; there is non-reconstruction at equality for either sign of the channel parameter. The Poisson advantage is averaged over trees and spins without conditioning on survival. This resolves the all-degree three-state regular-tree prediction. Combining the Poisson theorem with known tree-to-graph and algorithmic results gives the exact weak-recovery threshold for the symmetric three-community sparse stochastic block model with independent uniform labels, fixed within- and between-community rates \(a,b\gt 0\), and mean degree \((a+2b)/3\gt 1\): recovery is possible exactly when \((a-b)^2\gt 3(a+2b)\). Above this threshold it is achievable in \(O(n\log n)\) time; at or below it, weak recovery is information-theoretically impossible.