Bubeck–Ding–Eldan–Rácz high-dimensional indistinguishability conjecture

About 10 years old · traced to

Let G(n,d,p)G(n,d,p) be the spherical random geometric graph and let G(n,p)G(n,p) be the Erdős–Rényi random graph. For probability distributions on a finite set, define total variation distance by

TV⁡(μ,μ′)=12∑x∈Ω∣μ(x)−μ′(x)∣.\operatorname{TV}(\mu,\mu')=\frac{1}{2}\sum_{x\in\Omega}|\mu(x)-\mu'(x)|.

Write a≫ba\gg b to mean that a/b→∞a/b\to\infty as n→∞n\to\infty. Bubeck–Ding–Eldan–Rácz conjecture. If

d≫n3p3(log⁡1/p)3,d\gg n^3p^3(\log 1/p)^3,

then

TV⁡(G(n,p),G(n,d,p))→0\operatorname{TV}(G(n,p),G(n,d,p))\to 0

as n→∞n\to\infty. This is the high-dimensional, indistinguishable regime of the threshold problem for random geometric graphs. The source presents the statement as a conjecture and gives no resolution evidence for this exact formulation.

References

Primary source

Zach Hunter, Aleksa Milojević and Benny Sudakov, “Distinguishability threshold for random geometric graphs”, arXiv:2607.22480 (2026).

Additional references

3 papers in this index state this conjecture (2016–2026). The statement above is taken from the most recent of them; the others are arXiv:2203.15351, arXiv:1609.03511.

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.