---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '23155'
abstract:
- lang: eng
  text: "In this work we establish several monotonicity and decomposition results
    in the framework of random regular graphs. Among other results, we\r\nshow that,
    for a wide range of parameters d1 ≤ d2, there exists a coupling of\r\nG(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.\r\nOur contributions include
    new tools for analysing contiguity and total variation distance between random
    regular graph models, a novel procedure for\r\ngenerating 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,\r\nMcKay, Southwell and Zhukovskii."
acknowledgement: "We are grateful to Béla Bollobás, to Matthew Kwan and to Fabio\r\nToninelli
  for their helpful comments and suggestions, and to Nicholas Wormald for useful\r\nremarks
  on a preliminary version of this work and pointing us towards the reference [29].\r\nThe
  authors would also like to thank several anonymous referees for many useful suggestions,\r\nincluding
  pointing out that Lemma 2.10 already appeared in [11].\r\nPart of this research
  was done during a visit of the fourth author to IST Austria. We thank\r\nIST Austria
  for its hospitality.\r\nFor open access purposes, the authors have applied a CC
  BY public copyright license to\r\nany author accepted manuscript version arising
  from this submission. L. Hollom was supported by the Internal Graduate Studentship
  of Trinity College, Cambridge.\r\nL. Lichev was supported by the Austrian Science
  Fund (FWF) grant No. 10.55776/ESP624.\r\nA. Mond was supported by UK Research and
  Innovation grant MR/W007320/2. Wang was\r\nsupported by the ERC Starting Grant “RANDSTRUCT”
  No. 101076777."
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Lawrence
  full_name: Hollom, Lawrence
  last_name: Hollom
- first_name: Lyuben
  full_name: Lichev, Lyuben
  id: 9aa8388e-d003-11ee-8458-c4c1d7447977
  last_name: Lichev
- first_name: Adva
  full_name: Mond, Adva
  last_name: Mond
- first_name: Julien
  full_name: Portier, Julien
  last_name: Portier
- first_name: Yiting
  full_name: Wang, Yiting
  id: 1917d194-076e-11ed-97cd-837255f88785
  last_name: Wang
citation:
  ama: Hollom L, Lichev L, Mond A, Portier J, Wang Y. Monotonicity and decompositions
    of random regular graphs. <i>Annals of Applied Probability</i>. 2026;36(5):4716-4738.
    doi:<a href="https://doi.org/10.1214/26-AAP2345">10.1214/26-AAP2345</a>
  apa: Hollom, L., Lichev, L., Mond, A., Portier, J., &#38; Wang, Y. (2026). Monotonicity
    and decompositions of random regular graphs. <i>Annals of Applied Probability</i>.
    Institute of Mathematical Statistics. <a href="https://doi.org/10.1214/26-AAP2345">https://doi.org/10.1214/26-AAP2345</a>
  chicago: Hollom, Lawrence, Lyuben Lichev, Adva Mond, Julien Portier, and Yiting
    Wang. “Monotonicity and Decompositions of Random Regular Graphs.” <i>Annals of
    Applied Probability</i>. Institute of Mathematical Statistics, 2026. <a href="https://doi.org/10.1214/26-AAP2345">https://doi.org/10.1214/26-AAP2345</a>.
  ieee: L. Hollom, L. Lichev, A. Mond, J. Portier, and Y. Wang, “Monotonicity and
    decompositions of random regular graphs,” <i>Annals of Applied Probability</i>,
    vol. 36, no. 5. Institute of Mathematical Statistics, pp. 4716–4738, 2026.
  ista: 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.
  mla: Hollom, Lawrence, et al. “Monotonicity and Decompositions of Random Regular
    Graphs.” <i>Annals of Applied Probability</i>, vol. 36, no. 5, Institute of Mathematical
    Statistics, 2026, pp. 4716–38, doi:<a href="https://doi.org/10.1214/26-AAP2345">10.1214/26-AAP2345</a>.
  short: L. Hollom, L. Lichev, A. Mond, J. Portier, Y. Wang, Annals of Applied Probability
    36 (2026) 4716–4738.
das_tickbox: '0'
date_created: 2026-10-18T22:01:52Z
date_published: 2026-10-01T00:00:00Z
date_updated: 2026-10-19T07:39:17Z
day: '01'
ddc:
- '500'
department:
- _id: MaKw
- _id: GradSch
doi: 10.1214/26-AAP2345
external_id:
  arxiv:
  - '2505.22875'
file:
- access_level: open_access
  checksum: 46101e61d29cf40f0a204801d15a848f
  content_type: application/pdf
  creator: dernst
  date_created: 2026-10-19T07:33:58Z
  date_updated: 2026-10-19T07:33:58Z
  file_id: '23165'
  file_name: 2026_AnnalsAppliedProbability_Hollom.pdf
  file_size: 320593
  relation: main_file
  success: 1
file_date_updated: 2026-10-19T07:33:58Z
fulldoi: https://doi.org/10.1214/26-AAP2345
has_accepted_license: '1'
intvolume: '        36'
issue: '5'
keyword:
- Random regular graphs
- coupling
- contiguity
- total variation distance
- decomposition
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
mathsc:
- 05C80
month: '10'
oa: 1
oa_version: Published Version
page: 4716-4738
project:
- _id: bd95085b-d553-11ed-ba76-e55d3349be45
  grant_number: '101076777'
  name: Randomness and structure in combinatorics
- _id: e19fef4c-1f3d-11f0-ac04-b8b1af6886d8
  grant_number: E624
  name: THRESHOLDS IN SEMI-RANDOM PROCESSES AND GRAPH EMBEDDINGS
publication: Annals of Applied Probability
publication_identifier:
  eissn:
  - 2168-8737
  issn:
  - 1050-5164
publication_status: published
publisher: Institute of Mathematical Statistics
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Monotonicity and decompositions of random regular graphs
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 36
year: '2026'
...