Gao–Isaev–McKay embedding conjecture for random regular graphs

About 3 years old · traced to

Let G(n,d)\mathcal{G}(n,d) denote the uniform random labelled dd-regular graph. Let 0≤d1≤d≤n−10\leq d_1\leq d\leq n-1 be integers, excluding (d1,d)=(1,2)(d_1,d)=(1,2) and (d1,d)=(n−3,n−2)(d_1,d)=(n-3,n-2). Gao–Isaev–McKay embedding conjecture. There exists a coupling (Gd1,Gd)(\boldsymbol{G}_{d_1},\boldsymbol{G}_d) such that Gd1∼G(n,d1)\boldsymbol{G}_{d_1}\sim\mathcal{G}(n,d_1), Gd∼G(n,d)\boldsymbol{G}_d\sim\mathcal{G}(n,d), and

P(Gd1⊆Gd)=1−o(1).\mathbb{P}(\boldsymbol{G}_{d_1}\subseteq\boldsymbol{G}_d)=1-o(1).

The conjecture is known in several ranges of degrees, including the regimes listed in the paper, but remains open in full generality.

References

Primary source

Mikhail Isaev, Brendan D. McKay, Angus Southwell and Maksim Zhukovskii, “Sprinkling with random regular graphs”, arXiv:2309.00190 (2024).

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.