Sandwiching between random regular graphs and Erdős-Rényi graphs: configuration model and unions of perfect matchings
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909867973804032 |
|---|---|
| author | Gao, Pu Isaev, Mikhail Perez-Gimenez, Xavier |
| author_facet | Gao, Pu Isaev, Mikhail Perez-Gimenez, Xavier |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_21472 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sandwiching between random regular graphs and Erdős-Rényi graphs: configuration model and unions of perfect matchings Gao, Pu Isaev, Mikhail Perez-Gimenez, Xavier Combinatorics 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. |
| title | Sandwiching between random regular graphs and Erdős-Rényi graphs: configuration model and unions of perfect matchings |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2510.21472 |