Weighted matching Markov chain (${\pi }_{\lambda }(M)={\lambda }^{|M|}/Z_G(\lambda )$)

On the matchings in a graph, a lazy Markov chain proposes adding an edge, deleting an edge, or exchanging an edge for the unique matching edge incident with it. A proposal incident with two matching edges is rejected. Select the proposed edge uniformly and use the Metropolis–Hastings acceptance probability for the displayed weights. Symmetric proposals give detailed balance; deletions connect every state to the empty matching in a graph. The normalizing constant is the matching generating function.

Here the graph has $2n$ vertices and $m\ge 1$ edges. The bound is a deliberately loose canonical paths Poincare bound, sufficient for polynomial mixing time when both activity and reciprocal activity are polynomially bounded. Order the alternating graph paths and cycles of $I△F$ canonically. Convert each component from initial matching in a graph $I$ to final matching in a graph $F$ by moving an unmatched endpoint using exchanges; open a cycle with one deletion and finish it with one addition.

At an intermediate matching in a graph $M$, the complementary encoding $K=I△F△M$ is a matching in a graph away from the active component and has at most two degree-two vertices. Remove at most two edges to obtain a matching in a graph $K^{\prime }$. Record those edges and one bit selecting the initial alternating colour on the active component. For a fixed directed transition this data reconstructs $K$, $I△F$, the active component and its ordering, and then $I,F$; common edges are $M\cap K$. There are at most $2(m+1{)}^2$ auxiliary records per $K^{\prime }$.

If $d=|K|-|K^{\prime }|\le 2$, then ${\pi }_{\lambda }(I){\pi }_{\lambda }(F)={\lambda }^d{\pi }_{\lambda }(M){\pi }_{\lambda }(K^{\prime })$. The transition capacity is at least ${\pi }_{\lambda }(M)/(2m\max (\lambda ,{\lambda }^{-1}))$, and the path length is at most $4n$. Summing over the injective encodings proves the displayed path congestion bound.