= Solution
For $i=1,\ldots,n-1$, make one block from the edge weights $\{X_{ij}:j>i\}$. These $n-1$ blocks are independent because they contain disjoint edges. Changing one whole block only changes weights of edges incident with vertex $i$. Every <matching> contains at most one such edge, so its total weight changes by at most one. Comparing an old optimal <matching> in the new weights and a new optimal <matching> in the old weights proves that \b[the maximum <matching> weight also changes by at most one].
Apply the bounded-differences <martingale> argument to these $n-1$ blocks, giving
$$
\boxed{P(|W-EW|\ge t)\le2\exp\left(-\frac{t^2}{2(n-1)}\right)}.
$$
Exposing each edge separately would give a weaker quadratic-in-$n$ denominator. The grouped exposure is what supplies the requested linear denominator. The proof needs only independent weights in $[0,1]$, not identical uniform laws. For $n=1$, the <matching> weight is deterministically zero; the divided formula is intended for $n\ge2$.
\Image[/past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2007-matching-blocks.png]
{title=Independent blocks for revealing matching weights}
{description=Each edge is assigned to its lower-numbered endpoint. Edges in one block share a vertex, so any matching uses at most one of them.}
The general grouping argument is <vertex-block concentration of maximum matching weight>.
Back to article page
