2
$\begingroup$

I'm reading the Markov Chains and Mixing Times by David Levin et al.. In section 5.4 page 71 a proof is given for a bound of mixing time for the Metropolis Chain on graph coloring. In the proof, such statement is made that if $x$ and $y$ are colorings with $\rho(x,y) = r$, where $\rho(x,y)$ is the number of vertices where $x$ and $y$ disagree, there are colorings $x_0=x,x_1,\ldots,x_r=y$ such that $\rho(x_k,x_{k-1})=1$. However, suppose in a graph with only two vertices and an edge between them, $x$ is the coloring with one vertice red and the other black and $y$ stands for the reversed configuration, here $\rho(x,y) = 2$ but the transition from $x$ to $y$ can not be done within two steps. Am I missing something? If not, could this proof of mixing time bound be fixed?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.