Isaev–McKay–Southwell–Zhukovskii decomposition conjecture for random regular graphs

For integers d1,d2[1,n1]d_1,d_2\in[1,n-1] with d1d2d_1\le d_2, let G(n,d1)G(n,d2d1)G(n,d_1)\oplus G(n,d_2-d_1) be the random d2d_2-regular graph obtained by sampling independent random regular graphs of degrees d1d_1 and d2d1d_2-d_1, conditioning them to be edge-disjoint, and taking their union.

Isaev–McKay–Southwell–Zhukovskii conjecture. If d2=ω(1)d_2=\omega(1), then there exists a coupling of GG(n,d1)G(n,d2d1)G_{\oplus}\sim G(n,d_1)\oplus G(n,d_2-d_1) and GG(n,d2)G\sim G(n,d_2) such that

P(G=G)=1o(1).\mathbb{P}(G_{\oplus}=G)=1-o(1).

Equivalently, the disjoint-union model should be asymptotically indistinguishable from the uniform random d2d_2-regular graph in a strong coupling sense. The source attributes this conjecture to Isaev, McKay, Southwell and Zhukovskii and presents it as an additional restriction related to sprinkling; its general validity remains open.

Sources & referencesView supporting material

Primary source

Lawrence Hollom, Lyuben Lichev, Adva Mond, Julien Portier and Yiting Wang, “Monotonicity and decompositions of random regular graphs”, arXiv:2505.22875 (2025).

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.