Monotone coupling conjecture for random regular graphs

About 7 years old · traced to

Let nn be the number of vertices, and let 0≤d1≤d2≤n−10\le d_1\le d_2\le n-1 be integers such that d1nd_1n and d2nd_2n are even. Write G(n,di){\mathcal G}(n,d_i) for the uniformly random did_i-regular graph. A coupling (G1,G2)(G_1,G_2) is a joint realization with these marginal distributions. Monotone coupling conjecture. Except for (d1,d2)=(1,2)(d_1,d_2)=(1,2) and (d1,d2)=(n−3,n−2)(d_1,d_2)=(n-3,n-2), there exists a coupling (G1,G2)(G_1,G_2) such that

G1∼G(n,d1),G2∼G(n,d2),G_1\sim {\mathcal G}(n,d_1),\qquad G_2\sim {\mathcal G}(n,d_2),

and

P⁡(G1⊆G2)=1−o(1).\operatorname{\mathbb P}(G_1\subseteq G_2)=1-o(1).

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.

References

Primary source

Pu Gao, Mikhail Isaev and Brendan McKay, “Sandwiching random regular graphs between binomial random graphs”, arXiv:1906.02886 (2022).

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.