Sandwiching between random regular graphs and Erdős-Rényi graphs: configuration model and unions of perfect matchings

Abstract

We establish new couplings among several random graph and multigraph models related to the random regular graph $G(n,d)$, including the configuration model and unions of random perfect matchings. As a main result, we verify the Kim-Vusandwich conjecture for all large degrees $d=n-O({\log }^{4}n)$ and prove a weakened version for $d=O({\log }^{4}n)$, which are the only remaining open cases. Our approach introduces a coupling framework that links $G(n,d)$ and $G(n,p)$ through a chain of intermediate models.