= Solution
For any two states $X,Y$, the closed neighbourhood of $X\cup Y$ has at most $2s(\Delta+1)\leq2n/3$ vertices. The remaining induced graph therefore has at least $n/3$ vertices and maximum degree at most $\Delta$, so the <greedy independent-set bound> supplies an independent set $Z$ of size $s$ there. No vertex of $Z$ is adjacent to a vertex of $X\cup Y$. Replace the elements of $X$ one at a time by the elements of $Z$, and then replace the elements of $Z$ one at a time by those of $Y$. Every intermediate set is independent, and every prescribed swap has positive transition probability. Hence the chain is irreducible.
Solved by gpt-5.6-sol high.
Back to article page
