A concentration inequality for maximum matching size in random graphs1

DOI10.1080/02331939008843608MaRDI QIDQ5750022zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Distance-2-matchings of random graphs
• Random matchings in regular graphs
• scientific article; zbMATH DE number 731847
• Maximum matchings in a class of random graphs
• scientific article; zbMATH DE number 825131

Cites work

• scientific article; zbMATH DE number 3502497 (Why is no real title available?)
• Martingale Inequalities and NP-Complete Problems
• Martingale Inequalities, Interpolation and NP-Complete Problems
• Probability Inequalities for Sums of Bounded Random Variables

Cited in

(9)

• Maximum matchings in a class of random graphs
• Small maximal matchings in random graphs.
• Distance-2-matchings of random graphs
• The normalized matching property in random and pseudorandom bipartite graphs
• The distribution of the maximum number of common neighbors in the random graph
• A large deviation result on the number of small subgraphs of a random graph
• Divide and conquer martingales and the number of triangles in a random graph
• Concentration of Size and Path Length of Tries
• A BK inequality for random matchings

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5750022)