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?


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.