Sandwiching between random regular graphs and Erdős-Rényi graphs: configuration model and unions of perfect matchings
Preprint
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.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Sprinkling with random regular graphsElectronic Journal of Probability, 2025
- The number of perfect matchings, and the nesting properties, of random regular graphsRandom Structures & Algorithms, 2023
- Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivityRandom Structures & Algorithms, 2022
- Sandwiching random graphs: universality between random graph modelsAdvances in Mathematics, 2004
- Maximum matchings in a class of random graphsJournal of Combinatorial Theory, Series B, 1986
- A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular GraphsEuropean Journal of Combinatorics, 1980