---
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'
...
---
OA_place: repository
OA_type: green
_id: '4253'
abstract:
- lang: eng
  text: We consider a single genetic locus which carries two alleles, labelled P and
    Q. This locus experiences selection and mutation. It is linked to a second neutral
    locus with recombination rate r. If r = 0, this reduces to the study of a single
    selected locus. Assuming a Moran model for the population dynamics, we pass to
    a diffusion approximation and, assuming that the allele frequencies at the selected
    locus have reached stationarity, establish the joint generating function for the
    genealogy of a sample from the population and the frequency of the P allele. In
    essence this is the joint generating function for a coalescent and the random
    background in which it evolves. We use this to characterize, for the diffusion
    approximation, the probability of identity in state at the neutral locus of a
    sample of two individuals (whose type at the selected locus is known) as solutions
    to a system of ordinary differential equations. The only subtlety is to find the
    boundary conditions for this system. Finally, numerical examples are presented
    that illustrate the accuracy and predictions of the diffusion approximation. In
    particular, a comparison is made between this approach and one in which the frequencies
    at the selected locus are estimated by their value in the absence of fluctuations
    and a classical structured coalescent model is used.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Nicholas H
  full_name: Barton, Nicholas H
  id: 4880FE40-F248-11E8-B48F-1D18A9856A87
  last_name: Barton
  orcid: 0000-0002-8548-5240
- first_name: Alison
  full_name: Etheridge, Alison
  last_name: Etheridge
- first_name: Anja
  full_name: Sturm, Anja
  last_name: Sturm
citation:
  ama: Barton NH, Etheridge A, Sturm A. Coalescence in a Random Background. <i>Annals
    of Applied Probability</i>. 2004;14(2):754-785. doi:<a href="https://doi.org/10.1214/105051604000000099">10.1214/105051604000000099</a>
  apa: Barton, N. H., Etheridge, A., &#38; Sturm, A. (2004). Coalescence in a Random
    Background. <i>Annals of Applied Probability</i>. Institute of Mathematical Statistics.
    <a href="https://doi.org/10.1214/105051604000000099">https://doi.org/10.1214/105051604000000099</a>
  chicago: Barton, Nicholas H, Alison Etheridge, and Anja Sturm. “Coalescence in a
    Random Background.” <i>Annals of Applied Probability</i>. Institute of Mathematical
    Statistics, 2004. <a href="https://doi.org/10.1214/105051604000000099">https://doi.org/10.1214/105051604000000099</a>.
  ieee: N. H. Barton, A. Etheridge, and A. Sturm, “Coalescence in a Random Background,”
    <i>Annals of Applied Probability</i>, vol. 14, no. 2. Institute of Mathematical
    Statistics, pp. 754–785, 2004.
  ista: Barton NH, Etheridge A, Sturm A. 2004. Coalescence in a Random Background.
    Annals of Applied Probability. 14(2), 754–785.
  mla: Barton, Nicholas H., et al. “Coalescence in a Random Background.” <i>Annals
    of Applied Probability</i>, vol. 14, no. 2, Institute of Mathematical Statistics,
    2004, pp. 754–85, doi:<a href="https://doi.org/10.1214/105051604000000099">10.1214/105051604000000099</a>.
  short: N.H. Barton, A. Etheridge, A. Sturm, Annals of Applied Probability 14 (2004)
    754–785.
date_created: 2018-12-11T12:07:52Z
date_published: 2004-05-01T00:00:00Z
date_updated: 2026-05-29T09:59:37Z
day: '01'
doi: 10.1214/105051604000000099
extern: '1'
external_id:
  arxiv:
  - '0406174'
fulldoi: https://doi.org/10.1214/105051604000000099
intvolume: '        14'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: ' https://doi.org/10.48550/arXiv.math/0406174'
month: '05'
oa: 1
oa_version: Preprint
page: 754 - 785
publication: Annals of Applied Probability
publication_identifier:
  eissn:
  - 2168-8737
  issn:
  - 1050-5164
publication_status: published
publisher: Institute of Mathematical Statistics
publist_id: '1842'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Coalescence in a Random Background
type: journal_article
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 14
year: '2004'
...