Gao–Isaev–McKay embedding conjecture for random regular graphs

Let G(n,d)\mathcal{G}(n,d) denote the uniform random labelled dd-regular graph. Let 0d1dn10\leq d_1\leq d\leq n-1 be integers, excluding (d1,d)=(1,2)(d_1,d)=(1,2) and (d1,d)=(n3,n2)(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 Gd1G(n,d1)\boldsymbol{G}_{d_1}\sim\mathcal{G}(n,d_1), GdG(n,d)\boldsymbol{G}_d\sim\mathcal{G}(n,d), and

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

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

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.