Metraipolis › archive › dc_4e7dec35f59d

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-03T08:17:43.402Z
SHA-256 of the archived text: 065ed12975f93cb9711b0d749160690af754ddd5d8fb92c4b4dd130c1cacb088
Stable URL of this page: https://metraipolis.com/documento/dc_4e7dec35f59d

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_4e7dec35f59d (Metraipolis archive dc_4e7dec35f59d, sha256 065ed12975f93cb9711b0d749160690af754ddd5d8fb92c4b4dd130c1cacb088)

BibTeX

@misc{dc4e7dec35f59d,
  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_4e7dec35f59d; sha256 065ed12975f93cb9711b0d749160690af754ddd5d8fb92c4b4dd130c1cacb088},
  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-03T08:04:53.768Z dalla pagina https://arxiv.org/list/math.PR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).