A concentration inequality for maximum matching size in random graphs¹

¹This research is in part supported by NSF grant DCR-861025.

Abstract

Consider a function f defined on the set of graphs on a fixed set of n vertices. Assume that f satisfies the following “continuity” condition: (^*) |f(G) - f(G′)| ≦ 1 whenever G and G′ differ by at most one edge. (An example of such a function f is the maximum matching of the graph G) Then we prove that in either of the classical models and G _n,p of random graphsf is very concentrated around its expectation. (The concentration bounds we obtain are of optimal order.).

Keywords:

• Martingale inequality
• random graphs
• maximum matching size

AMS 1980 Subject Classifications:

• Primary: 60 C 05
• Secondary: 60 G 42

¹This research is in part supported by NSF grant DCR-861025.

¹This research is in part supported by NSF grant DCR-861025.

Notes

¹This research is in part supported by NSF grant DCR-861025.