Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2007 / B / 8

On this product, use the Hamming metric $d(x,y)=|\{i:x_i\ne y_i\}|$. The relevant Lipschitz condition is $|f(x)-f(y)|\le d(x,y)$, equivalently changing any one coordinate changes the function by at most one. More generally an $L$-Lipschitz function has bound $Ld(x,y)$. The unit version is the bounded-differences condition used below.

Azuma's inequality states that if $(M_i{)}_{i=0}^m$ is a martingale with $|M_i-M_{i-1}|\le 1$ almost surely, then for $t\ge 0$,For independent product coordinates $Z_1,\dots ,Z_m$, expose them successively and set $M_i=E[f(Z)\mid Z_1,\dots ,Z_i]$. If changing one coordinate changes $f$ by at most one, the possible conditional means at that exposure have diameter at most one, by averaging the same remaining independent coordinates. Therefore the martingale increments have absolute value at most one. It follows thatFor coordinate bounds $c_i$, the same argument gives denominator $2{\sum }_i{c}_i^2$. The argument extends to arbitrary independent measurable coordinates for an integrable function with these bounds, rather than requiring finite state sets.

The union area is a bounded measurable function of the centres, with $0\le X\le n\pi$. Fix all centres except one, and let $B$ be the union of the fixed disks. Replacing the remaining disk $D$ changes the area to $|B|+|D\setminus B|$. The second term always lies in $[0,\pi ]$, so the area changes by at most $\pi$, not merely by the weaker bound $2\pi$.

Thus $X/\pi$ has coordinate differences at most one for the $n$ independent centres. The preceding martingale bound givesOne may take $c=1/(2{\pi }^2)$, independently of all centre distributions. Boundedness of the area ensures the conditional expectations exist even when the centre locations have no finite moments.

For $i=1,\dots ,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 the maximum matching weight also changes by at most one.

Apply the bounded-differences martingale argument to these $n-1$ blocks, givingExposing 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\ge 2$.

The general grouping argument is vertex-block concentration of maximum matching weight.