Sandwiching dense random regular graphs between binomial random graphs
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.
- A characterization of the smallest eigenvalue of a graph
- A critical point for random graphs with a given degree sequence
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- Asymptotic enumeration by degree sequence of graphs of high degree
- Complex martingales and asymptotic enumeration
- Critical percolation on random regular graphs
- Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity
- scientific article; zbMATH DE number 3150484 (Why is no real title available?)
- scientific article; zbMATH DE number 3173143 (Why is no real title available?)
- scientific article; zbMATH DE number 3773632 (Why is no real title available?)
- scientific article; zbMATH DE number 1246230 (Why is no real title available?)
- scientific article; zbMATH DE number 1342092 (Why is no real title available?)
- Maximum likelihood estimation in the -model
- Random graphs with a given degree sequence
- Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity
- Random regular graphs of high degree
- Sandwiching random graphs: universality between random graph models
- Sandwiching random regular graphs between binomial random graphs
- Subgraphs of dense random graphs with specified degrees
- The number of graphs and a random graph with a given degree sequence
- The phase transition in random graphs: a simple proof
- Sandwiching biregular random graphs
- Degree sequences of sufficiently dense random uniform hypergraphs
- Correction to: ``Sandwiching dense random regular graphs between binomial random graphs
- On the restricted size Ramsey number for a pair of cycles
- The fractional chromatic number of random graphs
- Embedding theorems for random graphs with specified degrees
- Sprinkling with random regular graphs
This page was built for publication: Sandwiching dense random regular graphs between binomial random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2089753)
