Monotone coupling conjecture for random regular graphs
Monotone coupling conjecture for random regular graphs
Let be the number of vertices, and let be integers such that and are even. Write for the uniformly random -regular graph. A coupling is a joint realization with these marginal distributions. Monotone coupling conjecture. Except for and , there exists a coupling such that
and
This conjecture asks for asymptotically almost-sure containment whenever the larger regular degree is at least the smaller one. The weakened sandwich results cited in the paper do not imply this assertion, even when the degree gap is large.
Sources & referencesView supporting material
Primary source
Pu Gao, Mikhail Isaev and Brendan McKay, “Sandwiching random regular graphs between binomial random graphs”, arXiv:1906.02886 (2022).
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.