Markov chain algorithms for Eulerian orientations and 3-colourings of 2-dimensional Cartesian grids

Abstract In this paper we establish that the natural single point update Markov chain (also known as Glauber dynamics) for counting the number of Euler orientations of 2-dimensional Cartesian grids is rapidly mixing. This extends a result of Luby, Randall, and Sinclair (2001) who consider the case where orientations in the boundary are fixed. Similarly, we also obtain a rapid mixing result for the 3-colouring of rectangular Cartesian grids without fixing the boundaries. The proof uses path coupling and comparison to related Markov chains which allow additional transitions and which can be analysed directly.