Sampling 3-colourings of regular bipartite graphs. (English) Zbl 1126.05048

Galvin, David J.

Electron. J. Probab. 12, 481-497 (2007).

Summary: We show that if \(\Sigma=(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 \(\mathcal M\) is a Markov chain on the set of proper 3-colourings of \(\Sigma\) which updates the colour of at most \(\rho|V|\) vertices at each step and whose stationary distribution is uniform, then for \(\rho \approx .22\) and \(d\) sufficiently large the convergence to stationarity of \(\mathcal M\) is (essentially) exponential in \(|V|\). In particular, if \(\Sigma\) 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/(\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.

MSC:

05C15	Coloring of graphs and hypergraphs
82B20	Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics

Keywords:

mixing time; Potts model; conductance; Glauber dynamics; discrete hypercube