Sprinkling conjecture for random regular graphs
Sprinkling conjecture for random regular graphs
Let satisfy
Let be the set of pairs of edge-disjoint graphs on whose respective degrees are and , and let be uniform in this set. Write for the uniform random labelled -regular graph. Sprinkling conjecture. There is a coupling such that
and , , and . 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
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.