Monotonicity and decompositions of random regular graphs
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_ | 1866908383386271744 |
|---|---|
| author | Hollom, Lawrence Lichev, Lyuben Mond, Adva Portier, Julien Wang, Yiting |
| author_facet | Hollom, Lawrence Lichev, Lyuben Mond, Adva Portier, Julien Wang, Yiting |
| contents | In this work we establish several monotonicity and decomposition results in the framework of random regular graphs. Among other results, we show that, for a wide range of parameters $d_1 \leq d_2$, there exists a coupling of $G(n,d_1)$ and $G(n,d_2)$ satisfying that $G(n,d_1) \subseteq G(n,d_2)$ with high probability, confirming a conjecture of Gao, Isaev and McKay in a new regime. Our contributions include new tools for analysing contiguity and total variation distance between random regular graph models, a novel procedure for generating unions of random edge-disjoint perfect matchings, and refined estimates of Gao's bounds on the number of perfect matchings in random regular graphs. In addition, we make progress towards another conjecture of Isaev, McKay, Southwell and Zhukovskii. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_22875 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Monotonicity and decompositions of random regular graphs Hollom, Lawrence Lichev, Lyuben Mond, Adva Portier, Julien Wang, Yiting Combinatorics Probability 05C80 In this work we establish several monotonicity and decomposition results in the framework of random regular graphs. Among other results, we show that, for a wide range of parameters $d_1 \leq d_2$, there exists a coupling of $G(n,d_1)$ and $G(n,d_2)$ satisfying that $G(n,d_1) \subseteq G(n,d_2)$ with high probability, confirming a conjecture of Gao, Isaev and McKay in a new regime. Our contributions include new tools for analysing contiguity and total variation distance between random regular graph models, a novel procedure for generating unions of random edge-disjoint perfect matchings, and refined estimates of Gao's bounds on the number of perfect matchings in random regular graphs. In addition, we make progress towards another conjecture of Isaev, McKay, Southwell and Zhukovskii. |
| title | Monotonicity and decompositions of random regular graphs |
| topic | Combinatorics Probability 05C80 |
| url | https://arxiv.org/abs/2505.22875 |