= Vertex-block concentration of maximum matching weight
Give a graph on $n$ labelled vertices independent edge weights in $[0,1]$, and let $W$ be the maximum total weight of a <matching>. Put each edge into the block of its lower-numbered endpoint. There are at most $n-1$ independent blocks. Every matching uses at most one edge from any block, since the block's edges share that endpoint. Changing a whole block therefore changes the weight of each fixed matching by at most one. Comparing the old and new maximizing matchings shows the same bound for $W$.
The Doob exposure <martingale> for these blocks has increments bounded by one, so <Azuma's inequality> gives
$$
P(|W-EW|\ge t)\le2\exp\left(-\frac{t^2}{2(n-1)}\right),\qquad n\ge2.
$$
The important feature is grouping independent edge coordinates into vertex-centred blocks. Exposing all edges separately would give a weaker denominator of order $n^2$ on a dense graph. Identical distributions are unnecessary; independence and the common range bound suffice.
Back to article page
