Sprinkling with random regular graphs
This paper extends the idea of sprinkling to random regular graphs. Sprinkling is a tool that has been extensively used in the context of the binomial random graph \(G(n,p)\) on \(n\) vertices where each pair is included independently with probability \(p\). For \(p_1\), \(p_2\) such that \(p = p_1 +p_2 -p_1p_2\), one can expose \(G(n,p)\) as the union of two independent binomial random graphs on the same vertex set distributed as \(G(n,p_1)\) and \(G(n,p_2)\), respectively. Note that the choice of \(p_1\) and \(p_2\) is such that in the union of these two random graphs, the probability that there is an edge between a certain pair of vertices is \(p\). An analogous result for uniformly random regular graphs is far from obvious. Let \((G_1,G_2)\) be a pair of edge-disjoint graphs on the same vertex set of size \(n\), where \(G_1\) is \(d_1\)-regular and \(G_2\) is \(d_2\)-regular, selected uniformly at random among all such pairs. (We assume that \(d_1=d_1(n)\) and \(d_2 = d_2(n)\) are such that \(d_1n\) and \(d_2n\) are even.) It is conjectured that this random pair can be coupled with two uniformly random regular graphs \(G_{d_1}\) and \(G_{d_2}\) so that on the coupling space with probability \(1-o(1)\) as \(n\to \infty\), we have \(G_1 = G_{d_1}\), \(G_2 = G_{d_2}\) and \(G_{d_1+ d_2} = G_1 \cup G_2\). Here, it is assumed that \(d_1 + d_2 \leq n-1\) and \(\min \{d_1 + d_2, n-d_1, n-d_2 \}\to \infty\), as \(n\to \infty\). Another conjecture, along similar lines, is that if \(d_1+d_2 \leq n-1\) and \(d_1 + d_2 \to\infty\), the one can couple \(G_{d_1+d_2}\) with the union of two independent samples of \(G_{d_1}\) and \(G_{d_2}\) conditioned on being edge-disjoint, so that the two random graphs coincide on the coupling space with probability \(1-o(1)\), as \(n\to \infty\). (This implies the contiguity between the two random graphs which is known for \(d_1\), \(d_2\) fixed.)\N\NThe main result of the paper is a proof of these two conjectures for certain ranges of \(d_1\) and \(d_2\). These ranges include the cases where \(d_1=1\) but \(1 \ll d_2 =o(n^{1/3})\) and \(\min \{d_1,d_2, n- (d_1+d_2) \} \gg n/\log n\). The first case follows from what the authors call the reduction lemma. This states that the second conjecture holds iff the number of \(d_1\)-regular spanning subgraphs of \(G_{d_1+d_2}\) is not much smaller than its expected value. The authors also consider the asymptotics of this expected value, generalising the counting results of regular graphs, for \(d_1,d_2 \gg n/ \log n\).
- A proof of the Kahn-Kalai conjecture
- Asymptotic enumeration by degree sequence of graphs of high degree
- Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
- Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph
- Combinatorial estimates by the switching method
- Combinatorial theorems and integral matrices
- Counting extensions
- Couplings and matchings: combinatorial notes on Strassen's theorem
- Extremal subgraphs of random graphs
- Factorisation of the complete graph into spanning regular factors
- scientific article; zbMATH DE number 3168330 (Why is no real title available?)
- scientific article; zbMATH DE number 3906527 (Why is no real title available?)
- scientific article; zbMATH DE number 1342092 (Why is no real title available?)
- Improved bounds for the sunflower lemma
- Largest random component of a k-cube
- On the maximum number of common neighbours in dense random regular graphs
- Ramsey properties of random discrete structures
- Ramsey properties of random hypergraphs
- Random graphs.
- Random regular graphs of high degree
- Random Regular Graphs: Asymptotic Distributions and Contiguity
- Random subgraphs of finite graphs. III: The phase transition for the n-cube
- Sandwiching dense random regular graphs between binomial random graphs
- Sharp bounds on eigenvalues via spectral embedding based on signless Laplacians
- Subgraph counts for dense random graphs with specified degrees
- Subgraphs of dense random graphs with specified degrees
- The Existence of Probability Measures with Given Marginals
- The number of perfect matchings, and the nesting properties, of random regular graphs
- The probabilistic method
- The threshold for the square of a Hamilton cycle
This page was built for publication: Sprinkling with random regular graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7012654)
