= Canonical paths for the weighted matching chain
{title2=$\rho\leq16nm(m+1)^2\max(1,\lambda^2)\max(\lambda,\lambda^{-1})$}
Here the <graph> has $2n$ <vertices> and $m\geq1$ <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\triangle 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\triangle F\triangle 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'$. 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\triangle 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'$.
If $d=|K|-|K'|\leq2$, then $\pi_\lambda(I)\pi_\lambda(F)=\lambda^d\pi_\lambda(M)\pi_\lambda(K')$. 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.
Back to article page
