Kim--Vu's sandwich conjecture is true for $d\gg {\log }^{4}n$

Abstract

Kim and Vu made the following conjecture (\textit{Advances in Mathematics}, 2004): if $d\gg \log n$, then the random $d$-regular graph $G(n,d)$ can be ``sandwiched'' between $G(n,p_{\ast })$ and $G(n,p^{\ast })$ where $p_{\ast }$ and $p^{\ast }$ are both asymptotically equal to $d/n$. This famous conjecture was previously proved for all $d\gg (n\log n{)}^{3/4}$. In this paper, we confirm the conjecture when $d\gg {\log }^{4}n$. We also extend this result to near-regular degree sequences.

arXiv commentarXiv admin note: substantial text overlap with arXiv:1906.02886