Monotonicity and decompositions of random regular graphs
Hollom L, Lichev L, Mond A, Portier J, Wang Y. 2026. Monotonicity and decompositions of random regular graphs. Annals of Applied Probability. 36(5), 4716–4738.
Download
Journal Article
| Published
| English
Scopus indexed
Author
Hollom, Lawrence;
Lichev, LyubenISTA;
Mond, Adva;
Portier, Julien;
Wang, YitingISTA
Department
Grant
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 d1 ≤ d2, there exists a coupling of
G(n,d1) and G(n,d2) satisfying that G(n,d1) ⊆ G(n,d2) 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.
Mathematics Subject Classification
Publishing Year
Date Published
2026-10-01
Journal Title
Annals of Applied Probability
Publisher
Institute of Mathematical Statistics
Acknowledgement
We are grateful to Béla Bollobás, to Matthew Kwan and to Fabio
Toninelli for their helpful comments and suggestions, and to Nicholas Wormald for useful
remarks on a preliminary version of this work and pointing us towards the reference [29].
The authors would also like to thank several anonymous referees for many useful suggestions,
including pointing out that Lemma 2.10 already appeared in [11].
Part of this research was done during a visit of the fourth author to IST Austria. We thank
IST Austria for its hospitality.
For open access purposes, the authors have applied a CC BY public copyright license to
any author accepted manuscript version arising from this submission. L. Hollom was supported by the Internal Graduate Studentship of Trinity College, Cambridge.
L. Lichev was supported by the Austrian Science Fund (FWF) grant No. 10.55776/ESP624.
A. Mond was supported by UK Research and Innovation grant MR/W007320/2. Wang was
supported by the ERC Starting Grant “RANDSTRUCT” No. 101076777.
Volume
36
Issue
5
Page
4716-4738
ISSN
eISSN
IST-REx-ID
Cite this
Hollom L, Lichev L, Mond A, Portier J, Wang Y. Monotonicity and decompositions of random regular graphs. Annals of Applied Probability. 2026;36(5):4716-4738. doi:10.1214/26-AAP2345
Hollom, L., Lichev, L., Mond, A., Portier, J., & Wang, Y. (2026). Monotonicity and decompositions of random regular graphs. Annals of Applied Probability. Institute of Mathematical Statistics. https://doi.org/10.1214/26-AAP2345
Hollom, Lawrence, Lyuben Lichev, Adva Mond, Julien Portier, and Yiting Wang. “Monotonicity and Decompositions of Random Regular Graphs.” Annals of Applied Probability. Institute of Mathematical Statistics, 2026. https://doi.org/10.1214/26-AAP2345.
L. Hollom, L. Lichev, A. Mond, J. Portier, and Y. Wang, “Monotonicity and decompositions of random regular graphs,” Annals of Applied Probability, vol. 36, no. 5. Institute of Mathematical Statistics, pp. 4716–4738, 2026.
Hollom L, Lichev L, Mond A, Portier J, Wang Y. 2026. Monotonicity and decompositions of random regular graphs. Annals of Applied Probability. 36(5), 4716–4738.
Hollom, Lawrence, et al. “Monotonicity and Decompositions of Random Regular Graphs.” Annals of Applied Probability, vol. 36, no. 5, Institute of Mathematical Statistics, 2026, pp. 4716–38, doi:10.1214/26-AAP2345.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
2026_AnnalsAppliedProbability_Hollom.pdf
320.59 KB
Access Level
Open Access
Date Uploaded
2026-10-19
MD5 Checksum
46101e61d29cf40f0a204801d15a848f
arXiv 
Google Scholar