Expected regular-subgraph count conjecture for random regular graphs

Let Gd1+d2G(n,d1+d2)\boldsymbol{G}_{d_1+d_2}\sim\mathcal{G}(n,d_1+d_2), and let Rd1(G)\mathcal{R}_{d_1}(G) be the set of d1d_1-regular spanning subgraphs of GG. For d1,d2>0d_1,d_2>0 with d1+d2n1d_1+d_2\leq n-1, define λ:=d1/(d1+d2)\lambda:=d_1/(d_1+d_2). Expected regular-subgraph count conjecture.

ERd1(Gd1+d2)=(21/2e1/4+o(1))(λλ(1λ)1λ)n(d1+d2)/2(d1+d2d1)n.\mathbb{E}|\mathcal{R}_{d_1}(\boldsymbol{G}_{d_1+d_2})|=(2^{1/2}e^{1/4}+o(1))\bigl(\lambda^\lambda(1-\lambda)^{1-\lambda}\bigr)^{n(d_1+d_2)/2}\binom{d_1+d_2}{d_1}^{n}.

This conjecture generalises the known complete-graph enumeration formula and is proved in the paper when d1,d2=ω(n/logn)d_1,d_2=\omega(n/\log n); it remains open in general.

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.