{"id":"arxiv/2610.25507","url":"https://arxiv.org/abs/2610.25507","tags":["cs.DM","cs.DS","math.PR"],"score":0,"title":"Degree Stability of Parallel Greedy Matching in Random Graphs","domain":"cs.DM","source":"arxiv","authors":["Vishvajeet N","Shrinidhi Teganahally Sridhara"],"reviews":0,"subject":"cs.DM","summary":"We study a natural synchronous greedy matching process in Erdős-Rényi random graphs $\\mathbb{G}(n,p)$ and give a rigorous analysis of this parallel stochastic dynamics. The process evolves as follows: in each round, every unmatched vertex proposes to a uniformly random neighbour, and mutually proposing pairs are matched and removed from the graph, after which the process repeats on the residual graph. We consider the density regime $p=Θ(\\log^{1+ε} n/n)$ for any constant $ε>0$, which lies just above the threshold for the existence of a perfect matching. We show that, with high probability,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-18","reactions":{}}