Monotone coupling conjecture for random regular graphs

Let nn be the number of vertices, and let 0d1d2n10\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)=(n3,n2)(d_1,d_2)=(n-3,n-2), there exists a coupling (G1,G2)(G_1,G_2) such that

G1G(n,d1),G2G(n,d2),G_1\sim {\mathcal G}(n,d_1),\qquad G_2\sim {\mathcal G}(n,d_2),

and

P(G1G2)=1o(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.

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

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.