pipette
ESEspañol

Degree Stability of Parallel Greedy Matching in Random Graphs

Vishvajeet N, Shrinidhi Teganahally Sridhara

Preprint

In the authors' words

We study a natural synchronous greedy matching process in Erd\H{o}s-R\'enyi random graphs 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 for any constant , which lies just above the threshold for the existence of a perfect matching. We show that, with high probability, for rounds, every unmatched vertex keeps a constant fraction of its initial degree in the residual graph, simultaneously for all vertices and all rounds. By then, the process has matched a constant fraction of the vertices. Our analysis tracks fine-grained invariants that control the evolution of individual vertex degrees, rather than directly tracking the global degree distribution. At the local level, we analyze the per-round degree loss of a vertex via a neighbourhood-exposure martingale. We show that structural sparsity of yields variance and thus the per-round degree loss is strongly concentrated around its conditional expectation. At the global level, these local concentration bounds control the increments of a martingale tracking cumulative degree loss over many rounds, allowing us to show that vertex degrees remain stable for rounds.

Main resultLimitation the authors admit

Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 49 pages