Skip to content
DraconiticResearch
Search Sources API
186,541 studies31 sourcesUpdated 1 min ago
PreprintCC BY-SA 4.0arXiv

Maximum edge overlap between independent random regular graphs

  • Andrea D'Ascenzo
  • Riccardo Michielan
Open at sourcePDFDOICite

Abstract

Optimising the vertex correspondence can substantially increase the number of edges shared by two independent realisations of the same random graph. We quantify this phenomenon for uniformly random d-regular graphs and derive corresponding results for their edge-based graph edit distance. For every fixed d≥ 3, we show that the maximum overlap is n+Θℙ(n/log n), where the leading term n arises from Hamiltonicity, while the surplus captures the optimal order of the excess beyond it. We establish explicit upper and lower bounds on the surplus. The upper bound is obtained by counting common cores of minimum degree at least two, while the lower bound is established using spanning factors consisting of cycles of the same logarithmic length. For the special case d=2, we show that the maximum overlap is n−(1+oℙ(1))log n. The additional overlap achievable is also studied by rotating aligned Hamilton cycles, using a contiguity argument. As a by-product, we determine the asymptotic maximum overlap between unions of independent random perfect matchings under cyclic shifts.

Related

  1. Maximum cut and maximum bisection in random regular graphs
    P. M. Aronow, Patrick Lopatto
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  2. The maximum relaxation time of a random walk on regular graphs
    Haoran Zhu
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  3. The maximum number of triangles in regular graphs
    Ya-Hong Chen, Shi-Cai Gong, Changhong Lu +2
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. The Maximum Commute Time of Regular Graphs
    Jing Huang, Xuezhu Liao, Jiaxin Tang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Edge universality of random regular graphs of growing degrees
    Jiaoyang Huang, Horng‐Tzer Yau
    The Annals of ProbabilityPeer-reviewedLicence not statedFull text6 citedStatisticsOpenAlex

Cite

BibTeXRIS
BibTeX
@misc{dascenzo2026maximum,
  title = {{Maximum edge overlap between independent random regular graphs}},
  author = {Andrea D'Ascenzo and Riccardo Michielan},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.41735},
  eprint = {2610.41735},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41735},
  note = {CC BY-SA 4.0},
}
RIS
TY  - UNPB
TI  - Maximum edge overlap between independent random regular graphs
AU  - Andrea D'Ascenzo
AU  - Riccardo Michielan
PY  - 2026
DA  - 2026/10/30
PB  - arXiv
DO  - 10.48550/arxiv.2610.41735
UR  - https://arxiv.org/abs/2610.41735
AB  - Optimising the vertex correspondence can substantially increase the number of edges shared by two independent realisations of the same random graph. We quantify this phenomenon for uniformly random d-regular graphs and derive corresponding results for their edge-based graph edit distance. For every fixed d≥ 3, we show that the maximum overlap is n+Θ_ℙ(n/log n), where the leading term n arises from Hamiltonicity, while the surplus captures the optimal order of the excess beyond it. We establish explicit upper and lower bounds on the surplus. The upper bound is obtained by counting common cores of minimum degree at least two, while the lower bound is established using spanning factors consisting of cycles of the same logarithmic length. For the special case d=2, we show that the maximum overlap is n−(1+o_ℙ(1))log n. The additional overlap achievable is also studied by rotating aligned Hamilton cycles, using a contiguity argument. As a by-product, we determine the asymptotic maximum overlap between unions of independent random perfect matchings under cyclic shifts.
ER  -