Sandwiching dense random regular graphs between binomial random graphs (Q2089753)

This paper provides a breakthrough in the conjecture of \textit{J. H. Kim} and \textit{V. H. Vu} [Adv. Math. 188, No. 2, 444--469 (2004; Zbl 1050.05111)] that a sufficiently dense random \(d\)-regular graph can be approximated by binomial random graphs having edge probability approximately \(d/n\). More specifically the conjecture states that if \(d\gg \log n\), then the random regular graph \(G_{reg}(d,n)\) can be coupled with binomial random graphs \(G(n,p_1)\) and \(G(n,p_2)\), so that on the coupling space we have \(G(n,p_1) \subset G_{reg}(d,n) \subset G(n,p_2)\), with high probability as \(n\to \infty\). Here, \(p_1= (1-o(1))d/n\) and \(p_2= (1+o(1))d/n\). The authors prove this conjecture for \(d =d(n)\) such that \(\min \{d, n-d \}\gg n/\log n\). Furthermore, they prove the analogue of this for a random graph with a given degree sequence which is near-regular and dense. The former means that the difference between the maximum and the minimum degree is asymptotically smaller than the maximum degree. The latter means that the maximum degree is \(\Theta (n)\) but it is bounded away from \(n\). The main result that is used in the proof of the above theorems is an embedding theorem. Let \(\mathfrak{d}\) be a near-regular degree sequence on \(n\) vertices with maximum degree \(\Delta\). There is a \(p = (1-o(1)) \Delta /n\) for which there is a coupling between the random graphs \(G(\mathfrak{d})\) (the uniformly chosen random graphs among all graphs with this degree sequence) and \(G(n,p)\), in which the latter is a subgraph of the former with probability \(\to 1\) as \(n\to \infty\) (quite rapidly). The coupling is explicitly constructed.