A concentration inequality for maximum matching size in random graphs1

DOI10.1080/02331939008843608zbMath0718.60007OpenAlexW2095073488MaRDI QIDQ5750022

WanSoo T. Rhee

Publication date: 1990

Published in: Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/02331939008843608

zbMATH Keywords

Martingale inequalitiesmaximum matching of a graph on n verticesmodels of random graphs

Mathematics Subject Classification ID

Martingales with discrete parameter (60G42) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Cites Work

• Unnamed Item
• Martingale Inequalities, Interpolation and NP-Complete Problems
• Probability Inequalities for Sums of Bounded Random Variables
• Martingale Inequalities and NP-Complete Problems

This page was built for publication: A concentration inequality for maximum matching size in random graphs¹