Asymptotic equivalence conjecture for sums of random regular graphs

For d1,d2Nd_1,d_2\in\mathbb{N} with d1+d2n1d_1+d_2\leq n-1, let G(n,d)\mathcal{G}(n,d) denote the uniform random dd-regular graph. Let G(n,d1)G(n,d2)\mathcal{G}(n,d_1)\oplus\mathcal{G}(n,d_2) denote the distribution obtained by sampling independent random regular graphs of degrees d1d_1 and d2d_2, conditioned to be edge-disjoint. Asymptotic equivalence conjecture. If d1+d2d_1+d_2\rightarrow\infty, there is a coupling (G,Gd1+d2)(\boldsymbol{G}_{\oplus},\boldsymbol{G}_{d_1+d_2}) such that

GG(n,d1)G(n,d2),Gd1+d2G(n,d1+d2),\boldsymbol{G}_{\oplus}\sim\mathcal{G}(n,d_1)\oplus\mathcal{G}(n,d_2),\qquad \boldsymbol{G}_{d_1+d_2}\sim\mathcal{G}(n,d_1+d_2),

and

P(G=Gd1+d2)=1o(1).\mathbb{P}(\boldsymbol{G}_{\oplus}=\boldsymbol{G}_{d_1+d_2})=1-o(1).

For fixed positive degrees, only contiguity was previously known in the stated nonexceptional cases; the stronger coupling assertion remains open.

Sources & referencesView supporting material

Primary source

Mikhail Isaev, Brendan D. McKay, Angus Southwell and Maksim Zhukovskii, “Sprinkling with random regular graphs”, arXiv:2309.00190 (2024).

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.