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

The explanation

Start a rumor with one person, called the root. The rumor is one of three colors: red, green or blue. The root passes it to two children, each child passes it to two more, and so on forever. Each passing is noisy. With a strength setting λ = 1/2, a child keeps the parent's color with chance 2/3. It switches to each of the other two colors with chance 1/6. Now look only at the colors far down the tree, many generations later. Can you still guess the root's color better than chance?

This is the reconstruction problemSource 1. Two forces compete. Each step loses information, by a factor λ. But the number of descendants grows, by a factor d each generation. A classical count, the Kesten–Stigum bound, says you can guess well when d × λ² > 1. In the example, 2 × (1/2)² = 0.5, so the count gives no help. At λ = 1/√2, about 0.707, the product reaches exactly 1.

The bound always works in one direction. The question is whether it is also the exact cut-off, or whether clever guessing beats itSource 2. For five or more colors, Sly showed that clever guessing can beat itSource 3. For three colors, Sly proved the bound exact on regular trees with many children per personSource 4. Mossel, Sly and Sohn did the same for large random treesSource 5. Small trees were open.

The three-state paper claims the exact answer for every regular tree with at least two children, and every random Poisson tree with mean above one. A Poisson tree gives each person a random number of children with a set average. Guessing works exactly when d × λ² > 1, and fails at equality, for either sign of λSource 6. Negative λ means a child tends to avoid the parent's color. The paper says this settles the all-degree three-state predictionSource 7. At λ = −1/2, a child never keeps the parent's color, and each other color has chance 1/2. That is a random three-coloring. With four children, 4 × (−1/2)² = 1, so guessing fails there tooSource 8. For random trees the score is averaged over all trees, including ones that die outSource 9.

This has a network consequence. In a stochastic block model, people fall into three hidden groups. Pairs in the same group link at rate a, and pairs across groups at rate b. The paper claims that the groups can be partly recovered exactly when (a − b)² > 3(a + 2b). Above that line a fast method works, and at or below it no method can succeedSource 10. With a = 10 and b = 1, 81 is larger than 36, so recovery works. With a = 6 and b = 2, 16 is smaller than 30, so it fails.

A second paper treats four colors, where the channel favors staying the same. Four colors sit on the border between three, where the bound is exact, and five, where it is notSource 11. It claims guessing fails at and below the bound for every regular and Poisson tree, including equalitySource 12. This part is computer assisted. The probability arguments are written out, and exact-arithmetic programs check the remaining polynomial inequalitiesSource 13. Without the favoring of sameness, four colors can beat the boundSource 14. A third paper claims an exact test for four colors on any fixed tree with bounded branching. It needs no regular structure or growth rateSource 15.

The obstacle is that a far-off guess is not one number. It is a whole probability spread over the colorsSource 16. The papers track how that spread changes from one generation to the next. Showing it fades exactly at the bound is the hard step. Above the bound, a simple linear estimate already worksSource 17.

How sure is this? Lean, a computer proof checker, covers only part of the three-color result. It checks that guessing succeeds above the bound, on regular and Poisson trees. It does not cover failure at or below the bound, the network result, or the four-color papers. No specialist review of these papers has been published.

What it doesn't show. This does not cover four colors when the channel favors switching.