Kim--Vu's sandwich conjecture is true for d \geq \log^4 n

arXiv2011.09449MaRDI QIDQ6354048FDOQ6354048

Authors: Pu Gao, M. I. Isaev, Brendan D. McKay 

Publication date: 18 November 2020

Abstract: Kim and Vu made the following conjecture ( extit{Advances in Mathematics}, 2004): if $dgglogn$, 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 $dgg(nlogn{)}^{3/4}$. In this paper, we confirm the conjecture when $dgelo{g}^{4}n$. We also extend this result to near-regular degree sequences.

This page was built for publication: Kim--Vu's sandwich conjecture is true for $d \geq \log^4 n$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6354048)