Sampling 3-colourings of regular bipartite graphs

We show that if $\text{gS}=(V,E)$ is a regular bipartite graph for which the expansion of subsets of a single parity of $V$ is reasonably good and which satisfies a certain local condition (that the union of the neighbourhoods of adjacent vertices does not contain too many pairwise non-adjacent vertices), and if $\text{cM}$ is a Markov chain on the set of proper 3-colourings of $\text{gS}$ which updates the colour of at most $\rho \mathrm{\mid }V\mathrm{\mid }$ vertices at each step and whose stationary distribution is uniform, then for $\rho \approx .22$ and $d$ sufficiently large the convergence to stationarity of $\text{cM}$ is (essentially) exponential in $\mathrm{\mid }V\mathrm{\mid }$. In particular, if $\text{gS}$ is the $d$-dimensional hypercube $Q_d$ (the graph on vertex set $\{0,1{\}}^d$ in which two strings are adjacent if they differ on exactly one coordinate) then the convergence to stationarity of the well-known Glauber (single-site update) dynamics is exponentially slow in $2^d\mathrm{/}(\sqrt{d}\log d)$. A combinatorial corollary of our main result is that in a uniform 3-colouring of $Q_d$ there is an exponentially small probability (in $2^d$) that there is a colour $i$ such the proportion of vertices of the even subcube coloured $i$ differs from the proportion of the odd subcube coloured $i$ by at most $.22$. Our proof combines a conductance argument with combinatorial enumeration methods.