A Systematic Scan for 7-colourings of the Grid
A Systematic Scan for 7-colourings of the Grid
Markus Jalsenius
Department of Computer Science, University of Liverpool
Ashton Street, Liverpool, L69 3BX, United Kingdom
Kasper Pedersen
Department of Computer Science, University of Liverpool
Ashton Street, Liverpool, L69 3BX, United Kingdom
Abstract
We study the mixing time of a systematic scan Markov chain for sampling from
the uniform distribution on proper 7-colourings of a finite rectangular sub-grid
of the infinite square lattice, the grid. A systematic scan Markov chain cycles
through finite-size subsets of vertices in a deterministic order and updates the
colours assigned to the vertices of each subset. The systematic scan Markov chain
that we present cycles through subsets consisting of 2×2 sub-grids and updates the
colours assigned to the vertices using a procedure known as heat-bath. We give a
computer-assisted proof that this systematic scan Markov chain mixes in O(log n)
scans, where n is the size of the rectangular sub-grid. We make use of a heuristic to
compute required couplings of colourings of 2×2 sub-grids. This is the first time the
mixing time of a systematic scan Markov chain on the grid has been shown to mix
for less than 8 colours. We also give partial results that underline the challenges of
proving rapid mixing of a systematic scan Markov chain for sampling 6-colourings
of the grid by considering 2×3 and 3×3 sub-grids.
1 Introduction
This paper is concerned with sampling from the uniform distribution, π, on the set
of proper q-colourings of a finite-size rectangular grid. A q-colouring of a graph is an
assignment of a colour from a finite set of q distinct colours to each vertex and we say that
a colouring is a proper colouring if no two adjacent vertices are assigned the same colour.
Proper q-colourings of the grid correspond to the zero-temperature anti-ferromagnetic
q-state Potts model on the square lattice, a model of significant importance in statistical
physics (see for example Salas and Sokal [14]).
Sampling from π is computationally challenging, however it remains an important task
and it is frequently carried out in experimental work by physicists by simulating some
suitable random dynamics that converges to π. Ensuring that a dynamics converges to
π is generally straight forward, but obtaining good upper bounds on the number of steps
http://arxiv.org/abs/0704.1625v3
required for the dynamics to become sufficiently close to π is a much more difficult prob-
lem. Physicists are at times forced to “guess” (using some heuristic methods) the number
of steps required for their dynamics to be sufficiently close to the uniform distribution in
order to carry out their experiments. By establishing rigorous bounds on the convergence
rates (mixing time) of these dynamics computer scientists can provide underpinnings for
this type of experimental work and also allow a more structured approach to be taken.
Providing bounds on the mixing time of Markov chains is a well-studied problem in
theoretical computer science. However, the types of Markov chains frequently considered
by computer scientists do not always correspond to the dynamics usually used in the
experimental work by physicists. In computer science, the mixing time of various types
of random update Markov chains have been frequently analysed; notably on the grid by
Achlioptas, Molloy, Moore and van Bussel [1] and Goldberg, Martin and Paterson [9].
We say that a Markov chain on the set of colourings is a random update Markov chain
when one step of the the process consists of randomly selecting a set of vertices (often
a single vertex) and updating the colours assigned to those vertices according to some
well-defined distribution induced by π. Experimental work is, however, often carried out
by cycling through and updating the vertices (or subsets of vertices) in a deterministic
order. This type of dynamics has recently been studied by computer scientists in the
form of systematic scan Markov chains (systematic scan for short). For results regarding
systematic scan see for instance Dyer, Goldberg and Jerrum [5, 4] and Pedersen [12]
although these papers are not considering the grid specifically. It is important to note
that systematic scan remains a random process since the method used to update the
colour assigned to the selected set of vertices is a randomised procedure drawing from
some well-defined distribution induced by π.
In Section 3 we present a computer assisted proof that systematic scan mixes rapidly
when considering 7-colourings of the grid. Previously eight was the least number of
colours for which systematic scan on the grid was known to be rapidly mixing, due to
Pedersen [12], a result which we hence improve on in this paper. We will make use of
a recent result by Pedersen [12] to prove rapid mixing of systematic scan by bounding
the influence on a vertex (note that the literature traditionally talks about sites rather
than vertices). We will provide bounds on this influence parameter by using a heuristic
to mechanically construct sufficiently good couplings of proper colourings of a 2×2 sub-
grid. We will hence use a heuristic based computation in order to establish a rigorous
result about the mixing time of a systematic scan Markov chain. Finally, in Section 4,
we consider the possibility of proving rapid mixing of systematic scan for 6-colourings of
the grid by increasing the size of the sub-grids. We give lower bounds on the appropriate
influence parameter that imply that the proof technique we employ does not imply rapid
mixing of systematic scan for 6-colourings of the grid when using 2×2, 2×3 and 3×3
sub-grids.
1.1 Preliminaries and statement of results
Let Q = {1, . . . , 7} be the set of colours and V = {1, . . . , n} the set of vertices of a finite
rectangular grid G with toroidal boundary conditions. Working on the torus is common
practice as it avoids treating several technicalities regarding the vertices on the boundary
of a finite grid as special cases and hence lets us present the proof in a more “clean” way.
We point out however that these technicalities are straightforward to deal with (more
on this in Section 2). We formally say that a colouring σ of G is a function from V to
Q. Let Ω+ be the set of all colourings of G and Ω be the set of all proper q-colourings.
Then the distribution π, described earlier, is the uniform distribution on Ω. If σ ∈ Ω+
is a colouring and j ∈ V is a vertex then σj denotes the colour assigned to vertex j in
colouring σ. Furthermore, for a subset of vertices Λ ⊆ V and a colouring σ ∈ Ω+ we let
σΛ denote the colouring of the vertices in Λ under σ. For each vertex j ∈ V , let Sj denote
the set of pairs (σ, τ) ∈ Ω+ × Ω+ of colourings that only differ on the colour assigned to
vertex j, that is σi = τi for all i 6= j.
Let M be a Markov chain with state space Ω+ and stationary distribution π. Suppose
that the transition matrix of M is P . Then the mixing time from an initial colouring
σ ∈ Ω+ is the number of steps, that is applications of P , required for M to become
sufficiently close to π. Formally the mixing time of M from an initial colouring σ ∈ Ω+
is defined, as a function of the deviation ε from stationarity, by
Mixσ(M, ε) = min{t > 0 : dTV(P
t(σ, ·), π) ≤ ε}, (1)
where
dTV(θ1, θ2) =
|θ1(i)− θ2(i)| = max
|θ1(A)− θ2(A)| (2)
is the total variation distance between two distributions θ1 and θ2 on Ω
+. The mixing
time Mix(M, ε) of M is then obtained my maximising over all possible initial colourings
Mix(M, ε) = max
Mixσ(M, ε). (3)
We say that M is rapidly mixing if the mixing time of M is polynomial in n and log(ε−1).
We will make use of a recent result by Pedersen [12] to study the mixing time of a
systematic scan Markov chain for 7-colourings of the grid using block updates. We need
the following notation in order to define our systematic scan Markov chain. Define the
following set Θ = {Θ1, . . . ,Θm} of m blocks. Each block Θk ⊆ V is a 2×2 sub-grid and m
is the smallest integer such that
k=1Θk = V . For any block Θk and a pair of colourings
σ, τ ∈ Ω+ we write “σ = τ on Θk” if σi = τi for each i ∈ Θk and similarly “σ = τ off
Θk” if σi = τi for each i ∈ V \ Θk. We also let ∂Θk denote the set of vertices in V \ Θk
that are adjacent to some vertex in Θk, and we will refer to ∂Θk as the boundary of Θk.
Note from our previous definitions that σ∂Θk denotes the colouring of the boundary of
Θk under a colouring σ ∈ Ω
+. We will refer to σ∂Θk as a boundary colouring. Finally we
say that a 7-colouring of the 2×2 sub-grid Θk agrees with a boundary colouring σ∂Θk if
(1) no adjacent sites in Θk are assigned the same colour and (2) each vertex j ∈ Θk is
assigned a colour that is different to the colours of all boundary vertices adjacent to j.
For each block Θk and colouring σ ∈ Ω
+ let Ωk(σ) be the subset of Ω
+ such that
if σ′ ∈ Ωk(σ) then σ
′ = σ off Θk and σ
agrees with σ∂Θk . Let πk(σ) be the uniform
distribution on Ωk(σ). We then define P
[k] to be the transition matrix on the state space
Ω+ for performing a so-called heat-bath move on Θk. A heat-bath move on a block Θk,
given a colouring σ ∈ Ω+, is performed by drawing a new colouring from the distribution
πk(σ). Note in particular that applying P
[k] to a colouring σ ∈ Ω+ results in a colouring
σ′ ∈ Ω+ such that σ′ = σ off Θk and the colouring σ
of Θk is proper and agrees with
the colouring σ′∂Θk of the boundary of Θk (which is identical to σ∂Θk). We formally define
the following systematic scan Markov chain for 7-colourings of G, which systematically
performs heat-bath moves on 2×2 sub-grids, as follows. It is worth pointing out that this
holds for any ordering of the set of blocks.
Definition 1. The systematic scan dynamics for 7-colourings of G is a Markov chain
Mgrid with state space Ω
+ and transition matrix Pgrid = Π
It can be shown that the stationary distribution of Mgrid is π by considering the
construction of Pgrid. It is customary to refer to one application of Pgrid (that is updating
each block once) as one scan. One scan takes
|Θk| vertex updates and by construction
of Θ this sum is clearly of order O(n).
We will prove the following theorem and point out that this is the first proof of rapid
mixing of systematic scan for 7-colourings on the grid.
Theorem 2. Let Mgrid be the Markov chain from Definition 1 on 7-colourings of G.
Then the mixing time of Mgrid is
Mix(Mgrid, ε) ≤ 63 log(nε
−1). (4)
1.2 Context and related work
We now provide an overview of previous achievements for colourings of the grid. Previ-
ously it was known that systematic scan for q-colourings on general graphs with maximum
vertex degree ∆ mixes in O(logn) scans when q ≥ 2∆ due to Pedersen [12]. That result
is a hand-proof and uses block updates that updates the colour at each endpoint of an
edge during each step. Earlier Dyer et al. [4] had shown that a single-site systematic
scan Markov chain (where one vertex is updated at a time) mixes in O(logn) scans when
q > 2∆ and in O(n2 logn) scans when q = 2∆. It is hence well-established that system-
atic scan is rapidly mixing for q-colourings of the grid when q ≥ 8 but nothing has been
known about the mixing time for smaller q. The results of both Pedersen [12] and Dyer
et al. [4] bound the mixing time by studying the influence on a vertex. We will use that
technique in this paper as well, however we will construct the required couplings using a
heuristic. We defer the required definitions to Section 2 which also contains the proof of
Theorem 2.
Recent results have revealed that, in a single-site setting, one is not restricted use
the total influence on a vertex when analysing the mixing time of systematic scan by
bounding influence parameters. In a single-site setting one can define an n×n-matrix
whose entries are the influences that all vertices have on each other. Hayes [10] has
shown that providing a sufficiently small upper bound on the spectral gap of this matrix
implies rapid mixing of both systematic scan and random update. Dyer, Goldberg and
Jerrum [6] furthermore showed that an upper bound on any matrix norm also implies
rapid mixing of both types of Markov chains. These techniques are however not known
to apply to Markov chains using block moves. See the PhD thesis by Pedersen [13] for
more comprehensive review of the above results and for the difficulties in extending them
to cover block dynamics.
As random update Markov chains have received more attention than systematic scan
we also summarise some mixing results of interest regarding q-colourings of the grid (recall
that a random update Markov chain selects randomly a subset of sites to be updated at
each step). Achlioptas et al. [1] give a computer-assisted proof of mixing in O(n logn)
updates when q = 6 by considering blocks consisting of 2×3 sub-grids. Our computations
are similar in nature to the ones of Achlioptas et al. however their computations are not
sufficient to imply mixing of systematic scan as we will discuss in due course. More
recently Goldberg, Martin and Paterson [9] gave a hand-proof of mixing in O(n logn)
updates when q ≥ 7 using the technique of strong spatial mixing. Previously Salas and
Sokal [14] gave a computer-assisted proof of the q = 7 case, a result which was also
implied by another computer-assisted result due to Bubley, Dyer and Greenhill [3] that
applies to 4-regular triangle-free graphs. Finally it is worth pointing out that, in the
special case when q = 3, two complementary results of Luby, Randall and Sinclair [11]
and Goldberg, Martin and Paterson [8] give rapid mixing of random update.
2 Bounding the mixing time of systematic scan
This section will contain a proof of Theorem 2 although the proof of a crucial lemma,
which requires computer-assistance, is deferred to Section 3. We will bound the mixing
time of Mgrid by bounding the influence on a vertex, a parameter which we denote by
α and will define formally in due course. If α is sufficiently small then Theorem 2 from
Pedersen [12] implies that any systematic scan Markov chain, whose transition matrices
for updating each block satisfy two simple properties, mixes in O(logn) scans. For
completeness we restate this theorem (Theorem 3 below) and in the statement we let
M→ denote a systematic scan Markov chain whose transition matrices for each block
update satisfy the required properties.
Theorem 3. If α < 1 then the mixing time of M→ is
Mix(M→, ε) ≤
log(nε−1)
. (5)
For each block Θk the transition matrix P
[k] needs to satisfy the following two prop-
erties in order for Theorem 3 to apply.
1. If P [k](σ, τ) > 0 then σ = τ off Θk, and
2. π is invariant with respect to P [k].
It is pointed out in Pedersen [12] that if P [k] is a transition matrix performing a heat-bath
move then both of these properties are easily satisfied. Furthermore, it is pointed out
that when Ω is the set of proper colourings of a graph, then π is the uniform distribution
on Ω as we require. Since the transition matrices P [k] used in the definition of Mgrid
perform heat-bath updates we are hence able to use Theorem 3 to bound the mixing
time of Mgrid.
We are now ready to formally define the parameter α denoting the influence on a
vertex. For any pair of colourings (σ, τ) ∈ Si let Ψk(σ, τ) be a coupling of the distributions
induced by P [k](σ, ·) and P [k](τ, ·), namely πk(σ) and πk(τ) respectively. We remind
the reader that a coupling of two distributions π1 and π2 on state space Ω
+ is a joint
distribution Ω+ × Ω+ such that the marginal distributions are π1 and π2. For ease of
reference we also let pj(Ψk(σ, τ)) denote the probability that a vertex j ∈ Θk is assigned
a different colour in a pair of colourings drawn from some coupling Ψk(σ, τ). We then let
ρki,j = max
(σ,τ)∈Si
pj(Ψk(σ, τ)) (6)
be the influence of i on j under Θk. Finally the parameter α denoting the influence on
any vertex is defined as
α = max
ρki,j. (7)
Pedersen [12] actually defines α with a weight associated with each vertex, however as
we will not use weights in our proof we have omitted them from the above account. So, in
order to upper bound α we are required to upper bound the probability of a discrepancy
at each vertex j ∈ Θk under a coupling Ψk(σ, τ) of the distributions πk(σ) and πk(τ) for
any pair of colourings (σ, τ) ∈ Si that only differ at the colour of vertex i. Our main
task is hence to specify a coupling Ψk(σ, τ) of πk(σ) and πk(τ) for each pair of colourings
(σ, τ) ∈ Si and upper bound the probability of assigning a different colour to each vertex
in a pair of colourings drawn from that coupling.
Consider any block Θk and any pair of colourings (σ, τ) ∈ Si that differ only on the
colour assigned to some vertex i. Clearly the distribution on colourings of Θk, induced
by πk(σ) only depends on the boundary colouring σ∂Θk . Similarly, the distribution on
colourings of Θk, induced by πk(τ) depends only on τ∂Θk . If i 6∈ ∂Θk then the distributions
on the colourings of Θk, induced by πk(σ) and πk(τ), respectively, are the same and we
let Ψk(σ, τ) be the coupling in which any pair of colourings drawn from Ψk(σ, τ) agree
on Θk. That is, if the pair (σ
′, τ ′) of colourings are drawn from Ψk(σ, τ) then σ
′ = σ off
Θk, τ
′ = τ off Θk and σ
′ = τ ′ on Θk. This gives ρ
i,j = 0 for any i 6∈ ∂Θk and j ∈ Θk.
We now need to construct Ψk(σ, τ) for the case when i ∈ ∂Θk. For each j ∈ Θk
we need pj(Ψk(σ, τ)) to be sufficiently small in order to avoid ρ
i,j being too big. If the
ρki,j-values are too big the parameter α will be too big (that is greater than one) and we
cannot make use of Theorem 3 to show rapid mixing. Constructing Ψk(σ, τ) by hand such
that pj(Ψk(σ, τ)) is sufficiently small is a difficult task. It is, however, straight forward to
mechanically determine which colourings have positive measure in the distributions πk(σ)
and πk(τ) for a given pair of boundary colourings σ∂Θk and τ∂Θk . From these distributions
we can then use some suitable heuristic to construct a coupling that is good enough for
our purposes. We hence need to construct a specific coupling for each individual pair of
colourings differing only at a single vertex. In order to do this we will make use of the
following lemma, which is proved in Section 3.
Lemma 4. Let v1, . . . , v4 be the four vertices in a 2×2-block and z1, . . . , z8 be the boundary
vertices of the block and let the labeling be as in Figure 1. Let Z and Z ′ be any two 7-
colourings of the boundary vertices such that Z and Z ′ agree on each vertex except on z1.
Let πZ and πZ′ be the uniform distributions on proper 7-colourings of the block that agree
with Z and Z ′, respectively. For i = 1, . . . , 4 let pvi(Ψ) denote the probability that the
colour of vertex vi differ in a pair of colourings drawn from a coupling Ψ of πZ and πZ′.
Then there exists a coupling Ψ such that pv1(Ψ) < 0.283, pv2(Ψ) < 0.079, pv3(Ψ) < 0.051
and pv4(Ψ) < 0.079.
z4 z5
Figure 1: General labeling of the vertices in a 2×2-block Θk and the vertices ∂Θk on the
boundary of the block.
i (b)
Figure 2: A 2×2-block Θk showing all eight positions of a vertex i ∈ ∂Θk on the boundary
of the block in relation to a vertex j ∈ Θk in the block.
Thus if i ∈ ∂Θk we let Ψk(σ, τ) be the coupling of πk(σ) and πk(τ) that draws the
colouring of Θk from the coupling Ψ in Lemma 4, where Z is the boundary colouring
obtained from σ∂Θk and Z
′ is obtained from τ∂Θk , and leaves the colour of the remaining
vertices, V \Θk, unchanged. That is, if the pair (σ
′, τ ′) of colourings are drawn from
Ψk(σ, τ) then σ
′ = σ off Θk, τ
′ = τ off Θk and the colourings of Θk in σ
′ and τ ′ are
drawn from the coupling Ψ in Lemma 4 (see the proof for details on how to construct
Ψ). It is straightforward to verify that this is indeed a coupling of πk(σ) and πk(τ). Note
that due to the symmetry of the 2×2-block, with respect to rotation and mirroring, we
can always label the vertices of Θk and ∂Θk such that label z1 in Figure 1 represents the
discrepancy vertex i on the boundary. Hence we can make use of Lemma 4 to compute
upper bounds on the parameters ρki,j. We summarise the ρ
i,j-values in the following
Corollary of Lemma 4. Note that due to the symmetry of the block we can assume that
vertex j ∈ Θk in the corollary is located in the bottom left corner, as Figure 2 shows.
Corollary 5. Let Θk be any 2×2-block, let j ∈ Θk be any vertex in the block and let
i ∈ ∂Θk be a vertex on the boundary of the block. Then
ρki,j = max
(σ,τ)∈Si
pj(Ψk(σ, τ)) <
0.283, if i and j as in Figure 2(a) or (b),
0.079, if i and j as in Figure 2(c) or (h),
0.051, if i and j as in Figure 2(e) or (f),
0.079, if i and j as in Figure 2(d) or (g).
If i /∈ ∂Θk is not on the boundary of the block then ρ
i,j = 0.
We can then use Corollary 5 to prove Theorem 2. The proof of Theorem 2 is given
here:
Proof of Theorem 2. Let αk,j =
ρki,j be the influence on j under Θk. We need αk,j to
be upper bounded by one for each block Θk and vertex j ∈ Θk in order to ensure that
α = maxk maxj∈Θk αk,j is less than one. Fix any block Θk and any vertex j ∈ Θk. A
vertex i ∈ ∂Θk on the boundary of the block can occupy eight different positions on the
boundary in relation to j as showed in Figure 2(a)–(h). Recall that we are working on
the torus, and hence every vertex on the boundary of the block will belong to G. Thus,
using the bounds from Corollary 5 we have
αk,j =
ρki,j < 2(0.283 + 0.079 + 0.051 + 0.079) = 0.984. (9)
Then α = maxk maxj∈Θk αk,j < maxk 0.984 = 0.984 < 1 and we obtain the stated bound
on the mixing time of Mgrid by Theorem 3.
We make the following remark. In the proof of Theorem 2 above, we assume that G
is a finite rectangular grid with toroidal boundary conditions. Hence, every block is a
2×2-sub-grid and each vertex on the block boundary belongs to V . We note that if G
is a finite rectangular grid without toroidal boundary conditions then some vertices on
the boundary ∂Θk of a block Θk might fall outside G. The sum in Equation (9) is over
boundary vertices i that do belong to V , and hence the number of terms in this sum is
reduced if some boundary vertices do not belong to V , making α smaller. Furthermore,
if G is a non-rectangular region of the grid then a block next to the boundary might be
smaller than 2×2 vertices. Suppose Θk is a block that is smaller than 2×2 vertices. Then
the vertices that are missing in order to make Θk a full 2×2-block are boundary vertices.
Suppose i ∈ ∂Θk belongs to V and i
′ ∈ ∂Θk does not belong to V . When constructing
couplings Ψk(σ, τ), where (σ, τ) ∈ Si, we must consider the vertex i
′ as “colourless”,
which would decrease the value of pki,j . A more rigorous analysis yields that our mixing
result with seven colours and 2×2-blocks holds for arbitrary finite regions G of the grid.
Of course we have yet to establish a proof of Lemma 4, and the rest of this paper will be
concerned with this. Our method of proof uses some ideas of Goldberg, Jalsenius, Martin
and Paterson [7] in so far as it is computer assisted and we will be focusing on minimising
the probability of assigning different colours to vertex v1 in the constructed couplings.
We will however be required to construct a coupling on the 2×2 sub-grid, rather than
establishing bounds on the disagreement probability of a vertex adjacent to the initial
discrepancy and then extending this to a coupling on the whole block recursively. Our
approach is similar to the one Achlioptas et al. [1] take, however we do not have the
option of constructing an “optimal” coupling using a suitable linear program (even when
feasible) since our probabilities will be maximised over all boundary colourings. The
crucial difference between the approaches is that Achlioptas et al. [1] are using path
coupling (see Bubley and Dyer [2]) as a proof technique which requires them to bound
the expected Hamming distance between a pair of colourings drawn from a coupling. This
in turn enables them to, for a given boundary colouring, specify an “optimal” coupling
which minimises Hamming distance. We are, however, required to bound the influence of
i on j for each boundary colouring and sum over the maximum of these influences. The
reason for this is the inherit maximisation over boundary colourings in the definition of
ρki,j as described above.
Finally it is worth mentioning that providing bounds on the expected Hamming dis-
tance is similar to showing that the influence of a vertex is small and it is known that
this condition implies rapid mixing of a random update Markov chain, see for example
Weitz [15]. In a single-site setting the condition “the influence of a vertex is small” also
implies rapid mixing of systematic scan (Dyer et al. [4]), however, in a block setting this
condition is not sufficient to give rapid mixing of systematic scan (Pedersen [13]), which
is why we need to bound the influence on a vertex.
3 Constructing the coupling by machine
In order to prove Lemma 4 we will construct a coupling Ψ of πZ and πZ′ for all pairs of
boundary colourings Z and Z ′ that are identical on all boundary vertices but vertex z1,
on which Z and Z ′ differ. For each coupling constructed we verify that the probabilities
pvi(Ψ), i = 1, . . . , 4, are within the bounds of the lemma. The method is well suited to be
carried out with the help of a computer and we have implemented a program in C to do
so. Before stating the proof of Lemma 4 we will discuss how a coupling can be represented
by an edge-weighted complete bipartite graph. We make use of this representation of Ψ
in the proof of the lemma.
3.1 Representing a coupling as a bipartite graph
Let S be a set of objects and let W be a set of |S| pairs (s, ws) such that s ∈ S and ws ≥ 0
is a non-negative value representing the weight of s. Each element s ∈ S is contained
in exactly one of the pairs in W . If the value ws is an integer (which it is in our case)
it can be regarded as the multiplicity of s in a multiset. The set W is referred to as a
weighted set of S. Let πS,W be the distribution on S such that the probability of s is
proportional to ws, where (s, ws) is a pair in W . More precisely, the probability of s in
πS,W is PrπS,W (s) = ws/
(t,wt)∈W
wt. For example, let W be a weighted set of S and let
S ′ ⊆ S be a subset of S. Assume the weight ws = 0 if s ∈ S\S
′ and ws = k if s ∈ S
where k > 0 is a positive constant. Then πS,W is the uniform distribution on S
The reason for introducing the notion of a weighted set is that it can be used when
specifying a coupling of two distributions. Let S be a set and let W and W ′ be two
weighted sets of S such that the sum of the weights in W equals the sum of the weights
in W ′. Let wtot denote this sum. That is, wtot =
(s,ws)∈W
(s′,w′
)∈W ′ w
s′. The
two weighted sets W and W ′ define two distributions πS,W and πS,W ′ on S. We want
to specify a coupling Ψ of πS,W and πS,W ′. Let K|S|,|S| be an edge-weighted complete
bipartite graph with vertex sets W and W ′. That is, for each pair (s, ws) ∈ W there
is an edge to every pair in W ′. Every edge e of K|S|,|S| has a weight we ≥ 0 such that
the following condition holds. Let (s, ws) be any pair in W ∪ W
′ and let E be the set
of all |S| edges incident to (s, ws). Then
we = ws. It follows that the sum of the
edge weights of all |S|2 edges in K|S|,|S| equals wtot, the sum of the weights in W (and
W ′). The idea is that K|S|,|S| represents a coupling Ψ of πS,W and πS,W ′. In order to
draw a pair of elements from Ψ we randomly select an edge e in K|S|,|S| proportional to
its weight. The endpoints of e represent the elements in S drawn from πS,W and πS,W ′.
More precisely, the probability of choosing edge e in K|S|,|S| with weight we is we/wtot.
If edge e = ((s, ws), (s
′, w′s′)) is chosen it means that we have drawn s from πS,W and s
from πS,W ′, the marginal distributions of Ψ.
The bipartite graph representation of a coupling will be used when we construct
couplings of colourings of 2×2-blocks in the proof of Lemma 4.
3.2 The proof of Lemma 4
Here is the proof of Lemma 4:
Proof of Lemma 4. Fix two colourings Z and Z ′ of the boundary that differ on vertex
z1. Let c be the colour of vertex z1 in Z and let c
′ 6= c be the colour of z1 in Z
′. Let CZ
and CZ′ be the two sets of proper 7-colourings of the block that agree with Z and Z
respectively. Let C+ be the set of all 7-colourings of the block. Let WZ and WZ′ be two
weighted sets of C+. The weights are assigned as follows.
• For the pair (σ, wσ) ∈ WZ let the weight wσ = |CZ′| if σ ∈ CZ , otherwise let wσ = 0.
• For the pair (σ, wσ) ∈ WZ′ let the weight wσ = |CZ | if σ ∈ CZ′, otherwise let
wσ = 0.
It follows from the assignment of the weights that the distribution πC+,WZ is the uniform
distribution on CZ . That is, πC+,WZ = πZ . Similarly, πC+,WZ′ is the uniform distribution
πZ′ on CZ′. Note that the sum of the weights is |CZ||CZ′| in both WZ and WZ′. Then
a coupling Ψ of πC+,WZ and πC+,WZ′ can be specified with an edge-weighted complete
bipartite graph K = K|C+|,|C+|. For a given valid assignment of the weights of the edges
of K, making K represent a coupling Ψ, we can compute the probabilities of having a
mismatch on a vertex vi of the block when two colourings are drawn from Ψ. Let E be
the set of all edges e = ((σ, wσ), (σ
′, w′σ′)) in K such that σ and σ
′ differ on vertex vi.
Then pvi(Ψ) =
e∈E we/|CZ||CZ′|.
In order to obtain sufficiently small upper bounds on pvi(Ψ) for the four vertices
v1, . . . , v4 in the block we would like to assign weights to the edges of K such that much
weight is assigned to edges between colourings that agree on many vertices in the block.
In general it is not clear exactly how to assign weights to the edges. For instance, if
we assign too much weight to edges between colourings that are identical on vertex v2
we might not be able to assign as much weight as we would like to on edges between
colourings that are identical on vertex v4. Thus, the probability of having a mismatch
on v4 would increase. Intuitively a good strategy would be to assign as much weight as
possible to edges between colourings that are identical on the whole block. This implies
that we try to assign as much weight as possible to edges between colourings that are
identical on vertex v1, the vertex adjacent to the discrepancy vertex z1 on the boundary.
If there is a mismatch on vertex v1 it should be a good idea to assign as much weight
as possible to edges between colourings that are identical on the whole block apart from
vertex v1. This idea leads to a heuristic in which the assignment of the edge weights is
divided into three phases. The exact procedure is described as follows.
In phase one we match identical colourings. For all colourings σ ∈ C+ of the block
the edge e = ((σ, wσ), (σ, w
σ)) in K will be given weight we = min(wσ, w
σ). That is, we
maximise the probability of drawing the same colouring σ from both πC+,WZ and πC+,WZ′ .
For the following two phases we define an ordering of the colourings in C+. We order
the colourings lexicographically with respect to the vertex order v3, v2, v4, v1. That is,
if the seven colours are 1, . . . , 7 the colouring of v3, v2, v4, v1 will start with 1, 1, 1, 1,
respectively. The next colouring will be 1, 1, 1, 2, and so on. This ordering of colourings
in C+ carries over to an ordering of the pairs in WZ and WZ′. That is, we order the pairs
(σ, wσ) in WZ with respect to the lexicographical ordering of σ. Similarly we order the
pairs in WZ′ . This ordering of the pairs will be important in the next two phases. It
provides some control of how colourings are being paired up in terms of the assignment
of the weights on edges between pairs. Edges will be considered with respect to this
ordering because choosing an arbitrary ordering of the edges would not necessarily result
in probabilities pvi(Ψ) that would be within the bounds of the lemma.
In the second phase we ignore the colour of vertex v1 and match colourings that are
identical on all of the remaining three vertices v2, v3 and v4. More precisely, for each
pair (σ, wσ) ∈ WZ , considered in the ordering explained above, we consider the edges
e = ((σ, wσ), (σ
′, w′σ′)) where σ and σ
′ are identical on all vertices but v1. The edges are
considered in the ordering of the second component (σ′, w′σ′) ∈ WZ′. We assign as much
weight as possible to e such that the total weight on edges incident to (σ, wσ) ∈ WZ does
not exceed wσ and such that the total weight on edges incident to (σ
′, w′σ′) ∈ WZ′ does
not exceed w′σ′ . Note that in the lexicographical ordering of the colourings, vertex v1 is
the least significant vertex and therefore the ordering provides some level of control of
pairing up colourings that are similar on the remaining three vertices. It turns out that
the resulting coupling is sufficiently good for proving the lemma.
In the third and last phase we assign the remaining weights on the edges. As in phase
two, for each pair (σ, wσ) ∈ WZ we consider the edges e = ((σ, wσ), (σ
′, w′σ′)). The pairs
and edges are considered in accordance with the ordering explained above. The difference
between the second and third phase is that now we do not have any restrictions on the
colourings σ and σ′. We assign as much weight as possible to e such that the total weight
on edges incident to (σ, wσ) ∈ WZ does not exceed wσ and such that the total weight on
edges incident to (σ′, w′σ′) ∈ WZ′ does not exceed w
σ′. After phase three we have assigned
all weights to the edges of K and hence K represents a coupling Ψ of πZ and πZ′.
From K we compute the probabilities pv1(Ψ), pv2(Ψ), pv3(Ψ) and pv4(Ψ) as described
above. We have written a C-program which loops through all colourings Z and Z ′ of
the boundary of the block and constructs the bipartite graph K as described above.
For each boundary the probabilities pv1(Ψ), pv2(Ψ), pv3(Ψ) and pv4(Ψ) are successfully
verified to be within the bounds of the lemma. For details on the C-program, see
http://www.csc.liv.ac.uk/∼markus/systematicscan/.
4 Partial results for 6-colourings of the grid
In previous sections we have seen that systematic scan on the grid using 2×2-blocks and
seven colours mixes rapidly. An immediate question is whether we can do better and
show rapid mixing with six colours. This matter will be discussed in this section and we
will show that, even with bigger block sizes (up to 3×3), it is not possible to show rapid
mixing using the technique of this paper. More precisely, we will establish lower bounds
on the parameter α for 2×2-blocks, 2×3-blocks and 3×3-blocks. All three lower bounds
are greater than one and hence we cannot make use of Theorem 3 to show rapid mixing.
4.1 Establishing lower bounds for 2×2 blocks
We start by examining the 2×2-block again but this time with six colours. Lemma 4
provides upper bounds (under any colourings of the boundary) on the probabilities of
having discrepancies at each of the four vertices of the block when two 7-colourings are
drawn from the specified coupling. For six colours we will show lower bounds on these
probabilities under any coupling and a specified pair of boundary colourings. Once again,
let v1, . . . , v4 be the four vertices in a 2×2-block and let z1, . . . , z8 be the boundary vertices
of the block and let the labeling be as in Figure 1. Let Z and Z ′ be any two 6-colourings
of the boundary vertices that assign the same colour to each vertex except for z1. Let
πZ and πZ′ be the uniform distributions on the sets of proper 6-colourings of the block
that agree with Z and Z ′, respectively. Let Ψminvk (Z,Z
′) be a coupling of πZ and πZ′
that minimises pvk(Ψ). That is, pvk(Ψ) ≥ pvk(Ψ
(Z,Z ′)) for all couplings Ψ of πZ and
πZ′. Also let p
= maxZ,Z′ pvk(Ψ
(Z,Z ′)). We can hence say that there exist two
6-colourings Z and Z ′ of the boundary of a 2×2 block, that assign the same colour to
each vertex except for z1, such that pvk(Ψ) ≥ p
for any coupling Ψ of πZ and πZ′ . We
have the following lemma, which is proved by computation.
Lemma 6. Consider 6-colourings of the 2×2-block in Figure 1. Then plowv1 ≥ 0.379,
plowv2 ≥ 0.107, p
≥ 0.050 and plowv4 ≥ 0.107.
Proof. Fix one vertex vk in the block and fix two colourings Z and Z
′ of the boundary of
the block that differ only on the colour of vertex z1. Let CZ and CZ′ be the two sets of
proper 6-colourings of the block that agree with Z and Z ′, respectively. For c = 1, . . . , 6
let nc be the number of colourings in CZ in which vertex vk is assigned colour c. Similarly
let n′c be the number of colourings in CZ′ in which vertex vk is assigned colour c. It is
clear that the probability that vk is assigned colour c in a colouring σ
′ drawn from πZ
is PrπZ(σ
= c) = nc/|CZ|. For c = 1, . . . , 6 define mc = nc|CZ′|, m
c = n
c|CZ | and
M = |CZ||CZ′|. It follows that PrπZ(σ
= c) = mc/M and PrπZ′ (τ
= c) = m′c/M ,
where σ′ and τ ′ are colourings drawn from πZ and πZ′, respectively. Observe that the
quantities mc, m
c and M can be easily computed for a given pair of boundary colourings.
Now let Ψ be any coupling of πZ and πZ′ . It is easy to see that the probability that
vertex vk is coloured c in both colourings drawn from Ψ can be at most min(mc, m
c)/M .
Therefore, the probability of drawing two colourings from Ψ such that the colour of vertex
vk is the same in both colourings is at most
c=1,...,6
min(mc, m
c)/M , and the probability
of assigning different colours to vertex vk is at least pvk(Ψ) ≥ 1−
c=1,...,6min(mc, m
c)/M .
We have successfully verified the bounds in the statement of the lemma by maximising
the lower bound on pvk(Ψ) over all boundary colourings Z and Z
′ for each vertex vk
in the block. The computations are carried out with the help of a computer program
written in C. For details on the program, see http://www.csc.liv.ac.uk/∼markus/
systematicscan/.
For seven colours, Corollary 5 makes use of Lemma 4 to establish upper bounds on
the influence parameters ρki,j . These parameters are used in the proof of Theorem 2 to
obtain an upper bound on the parameter α. The upper bound on α is shown to be less
than one which implies rapid mixing for seven colours when applying Theorem 3. We can
use Lemma 6 to obtain lower bounds on the influence parameters ρki,j by completing the
coupling in a way analogous to the coupling in Corollary 5. This in turn will result in a
v1 v3v2z2
z4 z5 z6
z1 z9z10
v4 v5 v6
Figure 3: (a) General labeling of the vertices in a 2×3-block Θk and the vertices ∂Θk on
the boundary of the block. (b)–(c) All ten positions of a vertex i ∈ ∂Θk on the boundary
of the block in relation to a vertex j ∈ Θk in the corner of the block.
lower bound on the parameter α that is greater than one. That is, following the proof of
Theorem 2 and making use of Lemma 6, a lower bound on α will be
α ≥ 2(0.379 + 0.107 + 0.050 + 0.107) = 1.286 > 1. (10)
Hence we fail to show rapid mixing of systematic scan with six colours using 2×2-blocks.
4.2 Bigger blocks
We failed to show rapid mixing of systematic scan with six colours and 2×2-blocks and
we will now show that increasing the block size to both 2×3 and 3×3 will not be suf-
ficient either. Lemma 7 below considers 2×3-blocks and is analogous to Lemma 6. We
make use of the same notation as for Lemma 6, only the block is bigger and the label-
ing of the vertices is different (see Figure 3(a)). Lemma 7 is proved by computation
in the same way as Lemma 6. For details on the C-program used in the proof, see
http://www.csc.liv.ac.uk/∼markus/systematicscan/.
Lemma 7. Consider 6-colourings of the 2×3-block in Figure 3(a). Then plowv1 ≥ 0.3671,
plowv3 ≥ 0.0298, p
≥ 0.0997 and plowv6 ≥ 0.0174.
We will now use Lemma 7 to show that α > 1 for 2×3 blocks. Let Θk be any 2×3-
block and let j ∈ Θk be a vertex in a corner of the block. A vertex i ∈ ∂Θk on the
boundary of the block can occupy ten different positions on the boundary in relation to
j. See Figure 3(b) and (c). We can again determine lower bounds on the influences ρki,j
of i on j under Θk from Lemma 7. However, Lemma 7 provides lower bounds on ρ
i,j only
when i ∈ ∂Θk is adjacent to a corner vertex of the block, as in Figure 3(b). If i is located
as in Figure 3(c) we do not know more than that ρki,j is bounded from below by zero.
Nevertheless, the lower bound on α exceeds one. Let αk,j =
ρki,j be the influence on j
under Θk. Following the proof of Theorem 2 and using the lower bounds in Lemma 7 we
αk,j =
i in Fig. 3(b)
ρki,j +
i in Fig. 3(c)
ρki,j
≥ 2(0.3671 + 0.0298 + 0.0997 + 0.0174) = 1.028, (11)
where we set the lower bound on the second sum to zero. Now,
α = max
αk,j ≥ 1.028 > 1. (12)
v1 v3v2z2
z5 z6 z7
v4 v5 v6
z12 z11
v7 v8 v9
v1 v3v2
z6 z7 z8
z10v4 v5 v6
v7 v8 v9
z1 (c)
Figure 4: (a)–(b) General labeling of the vertices in a 3×3-block Θk and two different
labellings of the vertices ∂Θk on the boundary of the block. The discrepancy vertex
on the boundary has label z1. (b)–(c) All twelve positions of a vertex i ∈ ∂Θk on the
boundary of the block in relation to a vertex j ∈ Θk in the corner of the block.
Hence we cannot use Theorem 3 to show rapid mixing of systematic scan with six colours
and 2×3-blocks. It is interesting to note that considering 2×3-blocks was sufficient for
Achlioptas et al. [1] to prove mixing of a random update Markov chain for sampling
6-colourings of the grid.
Lastly, we increase the block size to 3×3 and show that a lower bound on α is still
greater than one. We have the following lemma which is proved by computation in the
same way as Lemmas 6 and 7. For details on the C-program used in the proof see
http://www.csc.liv.ac.uk/∼markus/systematicscan/.
Lemma 8. For 6-colourings of the 3×3-block with vertices labeled as in Figure 4(a) we
have plowv1 ≥ 0.3537, p
≥ 0.0245, plowv7 ≥ 0.0245 and p
≥ 0.0071. Furthermore,
for 6-colourings of the 3×3-block in Figure 4(b) we have plowv1 ≥ 0.0838, p
≥ 0.0838,
plowv7 ≥ 0.0138 and p
≥ 0.0138.
Note that Lemma 8 provides lower bounds on the probabilities of having a mismatch
on a corner vertex of the block when the discrepancy vertex on the boundary (labeled z1)
is adjacent to a corner vertex (Figure 4(a)) and adjacent to a middle vertex (Figure 4(b)).
Let Θk be any 3×3-block and let j ∈ Θk be a vertex in a corner of the block. A vertex
i ∈ ∂Θk on the boundary of the block can occupy twelve different positions on the
boundary in relation to j. See Figure 4(c) and (d). Analogous to Corollary 5 lower
bounds on the influences ρki,j of i on j under Θk can be determined from Lemma 8. Let
αk,j =
ρki,j be the influence on j under Θk. Following the proof of Theorem 2 and
using the lower bounds in Lemma 8 we have
αk,j =
i in Fig. 4(c)
ρki,j +
i in Fig. 4(d)
ρki,j
≥ 2(0.3537 + 0.0245 + 0.0245 + 0.0071) +
(0.0838 + 0.0838 + 0.0138 + 0.0138) = 1.0148. (13)
Thus, α = maxk maxj∈Θk αk,j ≥ 1.0148 > 1. Hence, we cannot use Theorem 3 to show
rapid mixing of systematic scan with six colours and 3×3-blocks.
A natural question is whether we can show rapid mixing using even bigger blocks. It
seems possible to do this although the computations rapidly become intractable as the
block size increases. Already with a 3×3-block the number of boundary colourings we
need to consider (after removing isomorphisms) is in excess of 106 and for each boundary
colouring there are more than 107 colourings of the block to consider. In addition to
simply generating the distributions on colourings of the block, the time it would take
to actually construct the required couplings, as we did in the proof of Lemma 4, would
also increase. Finally when using a larger block size, different positions of vertex j in
the block need to be considered whereas we could make use of to the symmetry of the
2×2-block to only consider one position of vertex j in the block. If different positions of
j have to be considered this has to be captured in the construction of the coupling and
would likely require more computations. The conclusion is that in order to show rapid
mixing for six colours of systematic scan on the grid we would most likely have to rely
on a different approach than the one presented in this paper.
References
[1] D. Achlioptas, M. Molloy, C. Moore, and F. Van Bussel. Sampling grid colorings
with fewer colours. In LATIN 2004: Theoretical Informatics, volume 2976 of Lecture
Notes in Computer Science, pages 80–89. Springer, 2004.
[2] R. Bubley and M. Dyer. Path coupling: a technique for proving rapid mixing in
Markov chains. In FOCS ’97: Proceedings of the 38th Symposium on Foundations
of Computer Science, pages 223–231. IEEE Computer Society Press, 1997.
[3] R. Bubley, M. Dyer, and C. Greenhill. Beating the 2∆ bound for approximately
counting colourings: A computer-assisted proof of rapid mixing. In SODA ’98:
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms,
pages 355–363. Society for Industrial and Applied Mathematics, 1998.
[4] M. Dyer, L. A. Goldberg, and M. Jerrum. Dobrushin conditions and systematic scan.
In Approximation, Randomization, and Combinatorial Optimization. Algorithms and
Techniques, volume 4110 of Lecture Notes in Computer Science, pages 327–338.
Springer, 2006.
[5] M. Dyer, L. A. Goldberg, and M. Jerrum. Systematic scan and sampling colourings.
Annals of Applied Probability, 16(1):185–230, 2006.
[6] M. Dyer, L. A. Goldberg, and M. Jerrum. Matrix norms and rapid mixing for spin
systems. To appear in the Annals of Applied Probability, 2008.
[7] L. A. Goldberg, M. Jalsenius, R. Martin, and M. Paterson. Improved mixing bounds
for the anti-ferromagnetic potts model on Z2. LMS Journal of Computation and
Mathematics, 9:1–20, 2006.
[8] L. A. Goldberg, R. Martin, and M. Paterson. Random sampling of 3-colourings in
2. Random Structures and Algorithms, 24(3):279–302, 2004.
[9] L. A. Goldberg, R. Martin, and M. Paterson. Strong spatial mixing with fewer
colours for lattice graphs. SIAM Journal on Computing, 35(2):486–517, 2005.
[10] T. P. Hayes. A simple condition implying rapid mixing of single-site dynamics on
spin systems. In FOCS ’06: Proceedings of the 47th Annual IEEE Symposium on
Foundations of Computer Science, pages 39–46. IEEE Computer Society Press, 2006.
[11] M. Luby, D. Randall, and A. Sinclair. Markov chain algorithms for planar lattice
structures. SIAM Journal on Computing, 31(1):167–192, 2001.
[12] K. Pedersen. Dobrushin conditions for systematic scan with block dynamics. In
Mathematical Foundations of Computer Science 2007, volume 4708 of Lecture Notes
in Computer Science, pages 264–275. Springer, 2007.
[13] K. Pedersen. On Systematic Scan. PhD thesis, University of Liverpool, 2008.
[14] J. Salas and A. D. Sokal. Absence of phase transition for antiferromagnetic Potts
models via the Dobrushin uniqueness theorem. Journal of Statistical Physics, 86(3–
4):551, 1997.
[15] D. Weitz. Combinatorial criteria for uniqueness of Gibbs measures. Random Struc-
tures and Algorithms, 27(4):445–475, 2005.
	Introduction
	Preliminaries and statement of results
	Context and related work
	Bounding the mixing time of systematic scan
	Constructing the coupling by machine
	Representing a coupling as a bipartite graph
	The proof of Lemma ??
	Partial results for 6-colourings of the grid 
	Establishing lower bounds for 22 blocks
	Bigger blocks
