{"id":"arxiv/2610.41735","url":"https://arxiv.org/abs/2610.41735","tags":["math.CO","cs.DM","math.PR"],"score":0,"title":"Maximum edge overlap between independent random regular graphs","domain":"math.CO","source":"arxiv","authors":["Andrea D'Ascenzo","Riccardo Michielan"],"reviews":0,"subject":"math.CO","summary":"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+Θ_{\\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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-30","reactions":{}}