Sprinkling with random regular graphs

Mikhail Isaev; Brendan D. McKay; Angus Southwell; Maksim Zhukovskii

doi:10.1214/25-EJP1272

Sprinkling with random regular graphs

Mikhail Isaev, Brendan D. McKay, Angus Southwell, Maksim Zhukovskii

School of Computing

Research output: Contribution to journal › Article › peer-review

Abstract

We conjecture that the distribution of the edge-disjoint union of two random regular graphs on the same vertex set is asymptotically equivalent to a random regular graph of the combined degree, provided it grows as the number of vertices tends to infinity. We verify this conjecture for the cases when the graphs are sufficiently dense or sparse. We also prove an asymptotic formula for the expected number of spanning regular subgraphs in a random regular graph.

Original language	English
Article number	17
Pages (from-to)	1-20
Number of pages	20
Journal	Electronic Journal of Probability
Volume	30
DOIs	https://doi.org/10.1214/25-EJP1272
Publication status	Published - 2025

Access to Document

10.1214/25-EJP1272

Cite this

@article{7554413586eb48d888770bc75f6c33d0,

title = "Sprinkling with random regular graphs",

abstract = "We conjecture that the distribution of the edge-disjoint union of two random regular graphs on the same vertex set is asymptotically equivalent to a random regular graph of the combined degree, provided it grows as the number of vertices tends to infinity. We verify this conjecture for the cases when the graphs are sufficiently dense or sparse. We also prove an asymptotic formula for the expected number of spanning regular subgraphs in a random regular graph.",

keywords = "Random regular graphs, Sandwich conjecture, Sprinkling",

author = "Mikhail Isaev and McKay, {Brendan D.} and Angus Southwell and Maksim Zhukovskii",

year = "2025",

doi = "10.1214/25-EJP1272",

language = "English",

volume = "30",

pages = "1--20",

journal = "Electronic Journal of Probability",

issn = "1083-6489",

publisher = "Institute of Mathematical Statistics",

}

TY - JOUR

T1 - Sprinkling with random regular graphs

AU - Isaev, Mikhail

AU - McKay, Brendan D.

AU - Southwell, Angus

AU - Zhukovskii, Maksim

PY - 2025

Y1 - 2025

N2 - We conjecture that the distribution of the edge-disjoint union of two random regular graphs on the same vertex set is asymptotically equivalent to a random regular graph of the combined degree, provided it grows as the number of vertices tends to infinity. We verify this conjecture for the cases when the graphs are sufficiently dense or sparse. We also prove an asymptotic formula for the expected number of spanning regular subgraphs in a random regular graph.

AB - We conjecture that the distribution of the edge-disjoint union of two random regular graphs on the same vertex set is asymptotically equivalent to a random regular graph of the combined degree, provided it grows as the number of vertices tends to infinity. We verify this conjecture for the cases when the graphs are sufficiently dense or sparse. We also prove an asymptotic formula for the expected number of spanning regular subgraphs in a random regular graph.

KW - Random regular graphs

KW - Sandwich conjecture

KW - Sprinkling

UR - http://www.scopus.com/inward/record.url?scp=85217547613&partnerID=8YFLogxK

U2 - 10.1214/25-EJP1272

DO - 10.1214/25-EJP1272

M3 - Article

AN - SCOPUS:85217547613

SN - 1083-6489

VL - 30

SP - 1

EP - 20

JO - Electronic Journal of Probability

JF - Electronic Journal of Probability

M1 - 17

ER -

Sprinkling with random regular graphs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this