Explicit perfect-matching threshold conjecture for randomly perturbed unbalanced complete bipartite graphs

Let $\alpha\in(0,1/2)$ be fixed and let $d=\alpha n$. For $p=C/n$, define $\gamma_*$ as the smallest root of

$$x=(1-\alpha)C\exp\bigl(-(1-\alpha)C\mathrm{e}^{-x}\bigr),$$

and define $\gamma^*=(1-\alpha)C\mathrm{e}^{-\gamma_*}$. The constant $C=C(\alpha)$ is the solution of

$$1-\frac{\gamma_*+\gamma^*+\gamma_*\gamma^*}{(2-2\alpha)C}=\frac{1-2\alpha}{2-2\alpha}.$$

Perfect-matching threshold conjecture. The sharp $d$-threshold for containing a perfect matching is $C/n$.

The formula comes from the asymptotic size of the largest matching in a sparse random graph, applied to $G(n-d,p)$. It gives an explicit prediction for the threshold that the preceding reduction identifies, but the paper does not prove it.