The sparse block-model coupling conjecture below the square-root threshold

Let 0δc0 \leq \delta \leq c. Define Q=G(n,κ1)\mathbf{Q}=G(n,\kappa_1) for the constant kernel κ1c\kappa_1\equiv c, and let P=G(n,κ2)\mathbf{P}=G(n,\kappa_2), where κ2\kappa_2 equals c+δc+\delta on [0,1/2]×[1/2,1][0,1/2]\times[1/2,1] and cδc-\delta elsewhere. Two models are essentially equivalent if they admit a coupling μ\mu such that

Eμd1(G,H)=o(n),\mathbf{E}_\mu d_1(G,H)=o(n),

where d1d_1 is edit distance and (G,H)μ(G,H)\sim\mu. The sparse block-model coupling conjecture. If δ<c\delta<\sqrt{c}, then P\mathbf{P} and Q\mathbf{Q} are essentially equivalent. This is the below-threshold half of the conjecture attributed to the authors of [BR11]; the preceding text notes that the claim is known in the range 0δ10\leq\delta\leq 1 with cδc\geq\delta, while its full stated range is not resolved here.

Sources & referencesView supporting material

Primary source

James Hirst, “Optimal couplings between sparse block models”, arXiv:1910.05442 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.