Monotonicity and decompositions of random regular graphs

Lawrence Hollom; Lyuben Lichev; Adva Mond; Julien Portier; Yiting Wang

paper

Monotonicity and decompositions of random regular graphs

arXiv:2505.22875

Abstract

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.