Metraipolis › archive › dc_3bd5e2e40dd5

Maximum edge overlap between independent random regular graphs — arXiv:2610.41735

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.41735
License (as archived)
CC0-1.0
Archived
2026-11-02T07:58:24.500Z
SHA-256 of the archived text
838f42fe01a346eef8e50c9acc04cbc6162866c35fdf860fd2f3fa10aa38dd46
Stable URL of this page
https://metraipolis.com/documento/dc_3bd5e2e40dd5

How to cite

Maximum edge overlap between independent random regular graphs — arXiv:2610.41735 — arXiv (en), https://arxiv.org/abs/2610.41735 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3bd5e2e40dd5 (Metraipolis archive dc_3bd5e2e40dd5, sha256 838f42fe01a346eef8e50c9acc04cbc6162866c35fdf860fd2f3fa10aa38dd46)
BibTeX
@misc{dc3bd5e2e40dd5,
  title = {Maximum edge overlap between independent random regular graphs — arXiv:2610.41735},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41735},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3bd5e2e40dd5; sha256 838f42fe01a346eef8e50c9acc04cbc6162866c35fdf860fd2f3fa10aa38dd46},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41735. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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\geq 3$, we show that the maximum overlap is $n+\Theta_{\mathbb P}(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_{\mathbb P}(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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.PR, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM); Probability (math.PR).
Pagina del lavoro: https://arxiv.org/abs/2610.41735 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-02T07:42:15.687Z dalla pagina https://arxiv.org/list/math.PR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).