Isaev–McKay–Southwell–Zhukovskii decomposition conjecture for random regular graphs
Isaev–McKay–Southwell–Zhukovskii decomposition conjecture for random regular graphs
For integers with , let be the random -regular graph obtained by sampling independent random regular graphs of degrees and , conditioning them to be edge-disjoint, and taking their union.
Isaev–McKay–Southwell–Zhukovskii conjecture. If , then there exists a coupling of and such that
Equivalently, the disjoint-union model should be asymptotically indistinguishable from the uniform random -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.