we-solve (beta)

Math-2920 · mathematics · Probability

The exact weak-recovery threshold for the symmetric three-community SBM

Status OpenLLM status Open unverified

Statement

Definitions and mathematical statement

Statement recorded in the supplied source.
For the sparse equal-size three-community stochastic block model with within-community probability a/n and between-community probability b/n, is weak recovery possible exactly when $(a-b)^2>3(a+2b)$? Above this threshold require an O(n log n) algorithm achieving overlap at least 1/3+epsilon with probability tending to one; at or below it require every graph-based randomized estimator’s expected overlap to tend to 1/3.

Short English statement

For the sparse equal-size three-community stochastic block model with within-community probability a/n and between-community probability b/n, is weak recovery possible exactly when $(a-b)^2>3(a+2b)$? Above this threshold require an O(n log n) algorithm achieving overlap at least 1/3+epsilon with probability tending to one; at or below it require every graph-based randomized estimator’s expected overlap to tend to 1/3.

Sources

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-2920-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-2920

The SBM corollary uses iid uniform latent labels (equal class sizes in expectation), positive fixed a,b and mean offspring d=(a+2b)/3>1. It does not state the exact-balanced class-size conditioning or all parameter regimes of this target. This entry records partial support; complete coverage of the question is not established by this catalogue.

The exact weak-recovery threshold for the symmetric three-community SBM

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

Go to contribution →