Degree Stability of Parallel Greedy Matching in Random Graphs
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,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.25507
curl -X POST /api/v1/records/arxiv/2610.25507/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.25507/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'