Metraipolis › archive › dc_ee3665b42e14
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-03T05:44:11.514Z
- SHA-256 of the archived text
3e0fb34117927a64611627a1f86820c945acb61147f2a88d5c0e49feaf0c1ca6- Stable URL of this page
https://metraipolis.com/documento/dc_ee3665b42e14
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_ee3665b42e14 (Metraipolis archive dc_ee3665b42e14, sha256 3e0fb34117927a64611627a1f86820c945acb61147f2a88d5c0e49feaf0c1ca6)
BibTeX
@misc{dcee3665b42e14,
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_ee3665b42e14; sha256 3e0fb34117927a64611627a1f86820c945acb61147f2a88d5c0e49feaf0c1ca6},
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-03T05:31:46.425Z dalla pagina https://arxiv.org/list/math.PR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).