{"id":"arxiv/2607.14948","url":"https://arxiv.org/abs/2607.14948","tags":["math.PR","math.ST"],"score":0,"title":"Graph alignment in sparse inhomogeneous models via self-overlap","domain":"math.PR","source":"arxiv","authors":["Louis Vassaux"],"reviews":0,"subject":"math.PR","summary":"We develop a general framework for understanding when graph alignment is information-theoretically feasible in sparse inhomogeneous random graph models, by studying the set of vertices on which the underlying matching can be recovered. Our main theorem gives a general lower bound on this set by leveraging the balanced load function introduced by Hajek (1990). The corresponding obstruction is captured by a new graph parameter, the self-overlap, which measures the extent to which a graph can imitate itself under a non-trivial relabelling. We then show that this criterion is sharp in a broad…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-16","reactions":{}}