{"id":"arxiv/2601.20020","url":"https://arxiv.org/abs/2601.20020","tags":["math.ST","math.PR","stat.CO","stat.ML"],"score":0,"title":"Matching and mixing: Matchability of graphs under Markovian error","domain":"math.ST","source":"arxiv","authors":["Zhirui Li","Keith D. Levin","Zhiang Zhao","Vince Lyzinski"],"reviews":0,"subject":"math.ST","summary":"We consider the problem of graph matching for a sequence of graphs generated under a time-dependent Markov chain noise model. Our edgelighter error model, a variant of the classical lamplighter random walk, iteratively corrupts the graph $G_0$ with edge-dependent noise, creating a sequence of noisy graph copies $(G_t)$. Much of the graph matching literature is focused on anonymization thresholds in edge-independent noise settings, and we establish novel anonymization thresholds in this edge-dependent noise setting when matching $G_0$ and $G_t$. Moreover, we also compare this anonymization…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-27","reactions":{}}