10 Lectures and 42 Open Problems — Detection Threshold for SBM for three of more communities

10 Lectures and 42 Open Problems — Detection Threshold for SBM for three of more communities

OpenAI's claim

OpenAI presents a mathematical result relevant to this question in the selected manuscript. Three-state symmetric broadcasting is claimed reconstructible precisely when $d\lambda^2>1$ on regular and observed Poisson trees, for both signs of the channel parameter.

Mathematical statement of the claimed result

Result 1.

The tree channel has three equally likely states and transition matrix with diagonal $(1+2\lambda)/3$ and off-diagonal $(1-\lambda)/3$, so $-1/2\le\lambda\le1$. On a regular tree with branching $b\ge2$, or a Poisson Galton--Watson tree of mean $d>1$, the claim gives \[ \text{reconstruction}\quad\Longleftrightarrow\quad d\lambda^2>1, \qquad d=b\text{ in the regular case}, \] with nonreconstruction at admissible equality. The SBM corollary fixes $a,b>0$, $(a+2b)/3>1$, assigns independent uniform labels in $\{1,2,3\}$, and uses edge probabilities $a/n$ within a label and $b/n$ across labels. For overlap maximized over label permutations, it claims \[ (a-b)^2\le3(a+2b)\ \Longrightarrow\ \mathbb E\operatorname{ov}(\sigma,\widehat\sigma_n)\to1/3 \] for every estimator from the graph and independent randomness. Under the strict reverse inequality, some $O(n\log n)$ algorithm achieves overlap at least $1/3+\varepsilon$ with probability tending to one. These SBM statements retain the mean-degree assumption. Reconstruction means $\lim_{\ell\to\infty}a_\ell>0$, where \[ a_\ell=\mathbb E\left\|\mathbb P(\sigma_{\varnothing}\in\cdot\mid T_{\le\ell},\sigma_{\partial T_\ell})-\operatorname{Unif}\{1,2,3\}\right\|_{\mathrm{TV}}. \] The tree shape in the conditioning is unlabelled. In the Galton--Watson case the expectation includes extinct trees; it is not conditioned on survival.

Outline of the argument

The posterior is represented by a complex mean and two invariant statistics. Fixed-point inequalities separately exclude positive and negative threshold reconstruction, and an exact finite certificate treats the coloring boundary; known transfer theorems then give the corresponding three-community graph recovery threshold.

Formal verification

For family 229, the three-state Comparator entries only establish reconstruction when $d\lambda^2>1$. They omit threshold nonreconstruction, the graph recovery corollary, and the four-state companions. The listed Comparator files are ThreeStateSupercritical.lean, ThreeStateTreeClauses.lean. The inventory does not supply a named declaration for these Comparator entries. This site has not executed the Lean code. The scope descriptions do not certify the remaining manuscript arguments.

Status caveat

OpenAI attributes these manuscripts to work by an internal model. Its release cautions that arguments without formalization can contain mistakes. This catalogue has not independently checked the proofs; the labels report the mathematical claims attributed to OpenAI.

Sources

• OpenAI, The exact reconstruction threshold for the three-state symmetric channel, 2026-09-25; citation key OAI:The-exact-reconstruction-threshold-for-the-three-state-symmetric-channel-September-25-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: cor:sbm; Statement source: thm:threshold.
• Family 229: Lean scope.
• Comparator ThreeStateSupercritical.json.
• Comparator ThreeStateSupercritical.lean.
• Comparator ThreeStateTreeClauses.json.
• Comparator ThreeStateTreeClauses.lean.
• OpenAI catalogue entry.