Sprinkling conjecture for random regular graphs

Let d1=d1(n),d2=d2(n)N:={0,1,}d_1=d_1(n),d_2=d_2(n)\in\mathbb{N}:=\{0,1,\ldots\} satisfy

d1+d2n1,min{d1+d2,nd1,nd2}.d_1+d_2\leq n-1,\qquad \min\{d_1+d_2,n-d_1,n-d_2\}\rightarrow\infty.

Let Sn(d1,d2)\mathcal{S}_n(d_1,d_2) be the set of pairs of edge-disjoint graphs on [n][n] whose respective degrees are d1d_1 and d2d_2, and let (G1,G2)(\boldsymbol{G}_1,\boldsymbol{G}_2) be uniform in this set. Write G(n,d)\mathcal{G}(n,d) for the uniform random labelled dd-regular graph. Sprinkling conjecture. There is a coupling (G1,G2,Gd1,Gd2,Gd1+d2)(\boldsymbol{G}_1,\boldsymbol{G}_2,\boldsymbol{G}_{d_1},\boldsymbol{G}_{d_2},\boldsymbol{G}_{d_1+d_2}) such that

P(Gd1=G1,Gd2=G2,Gd1+d2=G1G2)=1o(1),\mathbb{P}(\boldsymbol{G}_{d_1}=\boldsymbol{G}_1,\boldsymbol{G}_{d_2}=\boldsymbol{G}_2,\boldsymbol{G}_{d_1+d_2}=\boldsymbol{G}_1\cup\boldsymbol{G}_2)=1-o(1),

and Gd1G(n,d1)\boldsymbol{G}_{d_1}\sim\mathcal{G}(n,d_1), Gd2G(n,d2)\boldsymbol{G}_{d_2}\sim\mathcal{G}(n,d_2), and Gd1+d2G(n,d1+d2)\boldsymbol{G}_{d_1+d_2}\sim\mathcal{G}(n,d_1+d_2). This would establish that a random regular graph can asymptotically be sprinkled as two independent-looking edge-disjoint regular graphs; the conjecture is open in the stated generality.

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.