84 problems

In the sparse symmetric stochastic block model, let $q$ be the number of equal-sized communities, let $a,b>0$ be the within-community and between-community edge parameters, and def…

Consider the two-community stochastic block model with equal-sized communities and edge probabilities $p=\alpha\frac{\log n}{n}$ and $q=\beta\frac{\log n}{n}$, where $\alpha>\beta$…

Let $a>0$ be the average-degree parameter and let $\rho$ be the noise parameter, with $\rho=\epsilon$ and $\epsilon\in[0,1/2]$. In the sparse regime $p=a/n$, an estimator…

Let graphons be measurable symmetric functions representing limits of dense graphs, and let subgraph density constraints prescribe the densities of specified finite graphs. A stoch…

Exact-BP dichotomy conjecture. Exact BP should obey the same Kesten–Stigum dichotomy as the pairwise rule, with, below the threshold, a strictly faster saturation exponent than the…

YLS24+'s conjecture. The same threshold remains valid when the average degrees $\lambda_\ell$ are constant.

Quasirandomness conjecture. There exists a constant-degree polynomial test that distinguishes these hypotheses with high probability if and only if one of the signed subgraph count…

Let $\theta=\sqrt{\alpha_n}{\bf 1}_n$ under the null hypothesis and $\sqrt{\alpha_n}\bigl({\bf 1}_n+c\cdot n^{-5/4}\alpha_n^{-3/4}\eta\bigr)$ under the alternative, where…

Degree-profiling conjecture. Replacing the community-recovery algorithm used in this work by the degree-profiling algorithm gives an efficient graph-matching algorithm in the gener…

Bethe-Hessian community-detection conjecture. Above the Kesten–Stigum threshold, the number of negative outlier eigenvalues of $H(\pm\sqrt{d})$ can consistently estimate the number…

The pair-approximation approach describes the stochastic epidemic exactly on locally tree-like graphs. Pair-approximation exactness conjecture. The pair approximation is conjecture…

Let $H=\mathbb{K}_3$ be the triangle, and let $T_{N,2}(H)$ denote the corresponding ego-centric network-sampling statistic. Let $U$ be the region of sparsity parameters shown in Fi…

Consider a stochastic block model in the sparse regime where the average degree is of constant order, and let the Kesten–Stigum threshold be $d_{\mathrm{KS}}=\lambda^{-2}$. ACKZ's…

Let $d$ be the average degree and let $d_{\tiny\textsf{\textup{KS}}}:=\lambda^{-2}$ denote the Kesten–Stigum threshold. DKMZ's conjecture. Above the Kesten–Stigum threshold,…

Let $I'(\lambda,p,q)=2\lambda\left[1-\sqrt{pq}-\sqrt{(1-p)(1-q)}\right]$ be the information quantity governing exact community recovery in the logarithmic regime for the geometric…

Exact-matching conjecture. If $G_1\cap G'_2$ has no isolated vertex, then exact graph matching may be possible.

Consider a stochastic block model with $k$ communities, within-community edge probability $p$, between-community edge probability $q$, and parameters in the sparse asymptotic regim…

Abbe et al.'s tightness conjecture. The impossibility result is tight: exact recovery is achievable whenever

Sharp phase-transition conjecture. For any sufficiently large constant $L(p,q)>0$, if

Full-power testing conjecture. Given the expression of $\beta_n$ in the phase transition, a test with asymptotically full power may be constructed from a weighted combination of

Let $G_1,\ldots,G_m$ be multiple correlated stochastic block models, and compare community detection with the corresponding single-SBM setting. Correlated-SBM threshold conjecture.…

Let $G_1$ and $G_2$ be correlated stochastic block models, and consider the problem of recovering their communities in regimes of exact, almost exact, or partial recovery. Correlat…

Let the planted bisection model have two equally sized communities on $2n$ vertices, with within-community edge probability $p_n=c_n/n$ and between-community edge probability…

Let $G_1$ and $G_2$ be correlated stochastic block model graphs with community assignment $\boldsymbol{\boldsymbol{\sigma}}$, parameters $\alpha$, $\beta$, and correlation paramete…

Let $T$ be a regular tree or a Galton-Watson tree with Poisson offspring distribution, with root vertex $\rho$. Let $(T,\rho,\theta,W)$ denote the corresponding broadcast model wit…