Sharpness of the Kesten-Stigum reconstruction threshold for three-state symmetric and ferromagnetic four-state Potts channels on trees

Three-state theorem: for the symmetric channel with $-1/2\le\lambda\le1$, on every $b$-ary tree ($b\ge2$) and every observed Poisson($d$) tree with $d>1$, reconstruction holds iff $d\lambda^2>1$, with non-reconstruction at equality for both signs (so the 3-coloring channel is non-reconstructible at branching four). Corollary: weak recovery in the symmetric three-community sparse block model is possible iff $(a-b)^2>3(a+2b)$. Four-state theorem: for the ferromagnetic channel ($0\le\lambda\le1$), non-reconstruction whenever $d\lambda^2\le1$ on $d$-ary and Poisson trees. Companion: an $L^3$-capacity criterion for four-state reconstruction on bounded-degree trees. Not shown: the antiferromagnetic four-state channel.

Three-state theorem: for the symmetric channel with $-1/2\le\lambda\le1$, on every $b$-ary tree ($b\ge2$) and every observed Poisson($d$) tree with $d>1$, reconstruction holds iff $d\lambda^2>1$, with non-reconstruction at equality for both signs (so the 3-coloring channel is non-reconstructible at branching four). Corollary: weak recovery in the symmetric three-community sparse block model is possible iff $(a-b)^2>3(a+2b)$. Four-state theorem: for the ferromagnetic channel ($0\le\lambda\le1$), non-reconstruction whenever $d\lambda^2\le1$ on $d$-ary and Poisson trees. Companion: an $L^3$-capacity criterion for four-state reconstruction on bounded-degree trees. Not shown: the antiferromagnetic four-state channel.