A Non-Markovian Coupling for Randomly Sampling Colorings

Thomas P. Hayes ^{∗}  Eric Vigoda^{†}

July 18, 2005

Abstract

We study a simple Markov chain, known as the Glauber dynamics, for randomly sampling (proper) k-colorings of an input graph G on n vertices with maximum degree Δ and girth g. We prove the Glauber dynamics is close to the uniform distribution after O(n log n) steps whenever k > (1 + ϵ)Δ, for all ϵ > 0, assuming g ≥ 11 and Δ = Ω(log n). The best previously known bounds were k > 11Δ/6 for general graphs, and k > 1.489Δ for graphs satisfying girth and maximum degree requirements.

Our proof relies on the construction and analysis of a non-Markovian coupling. This appears to be the first application of a non-Markovian coupling to substantially improve upon known results.

∗Division of Computer Science, University of California at Berkeley. Email: hayest@cs.uchicago.edu.

†College of Computing, Georgia Institute of Technology. Email: vigoda@cc.gatech.edu ∗Department of Computer Science, University of Chicago, Chicago, IL 60637,

{hayest,vigoda}@cs.uchicago.edu. The majority of this research was conducted while the authors were at the University of Chicago, Department of Computer Science, and partially, while the second author was visiting the Isaac Newton Institute for Mathematical Sciences, Cambridge, UK. This work was supported by NSF Grant CCR-0237834. A preliminary version of this paper appeared in Proceedings of the 44th Annual Symposium on Foundations of Computer Science (FOCS), 618-627, 2003.

1 Introduction

1.1 Overview

Given a graph G = (V, E) with maximum degree Δ, is there an algorithm which randomly generates a k-coloring whenever k > Δ and runs in time polynomial in the size of G? A k-coloring is an assignment of colors to vertices σ : V → [k] such that each pair of adjacent vertices receives two distinct colors. Although constructing such a coloring is trivial provided k > Δ, even with this many colors the sampling problem seems difficult.

This problem has received considerable attention in the Computer Science, Discrete Mathematics and Statistical Physics communities. (In Statistical Physics jargon, we want to efficiently simulate the Gibbs distribution of the zero-temperature anti-ferromagnetic Potts model [19].) Efficient sampling algorithms are central to approximation algorithms for the corresponding #P-complete counting problem (estimating the number of k-colorings), see [15].

It is widely believed there is an efficient scheme for sampling colorings whenever k ≥ Δ + 2. Surprisingly, the following very simple Markov process likely suffices. The Markov chain, popular in the Statistical Physics community, is known as the Glauber dynamics (Metropolis version). From a coloring X_{t} ∈ Ω, we perform the following transition X_{t} → X_{t+1}:

• Choose a vertex v and color c uniformly at random from V and [k] respectively.

• Set X_{t+1}(z) = X_{t}(z) for all z ≠ v.

• If no neighbors of v have color c in X_{t+1}, then set X_{t+1}(v) = c, otherwise set X_{t+1}(v) = X_{t}(v).

It is straightforward to verify that the Glauber dynamics for all k ≥ Δ + 2 is ergodic and time-reversible with unique stationary distribution uniformly distributed over Ω.

Our goal is to analyze the mixing time of the Glauber dynamics. Roughly speaking, the mixing time is the number of transitions until the chain is close to stationarity from an arbitrary initial coloring; see Section 2.1 for a formal definition. Fast convergence of the Glauber dynamics has implications for phase transitions in the Potts model, e.g., see [3, 10].

The first significant progress was by Jerrum [15], proving the mixing time is O(n log n) whenever k > 2Δ. Independently, Salas and Sokal [19] proved closely related results about phase transitions in the Potts model. Vigoda [20] improved these results to k > 11Δ/6 via analysis of a more complicated Markov chain, which implied O(n^{2}) mixing time of the Glauber dynamics.

Dyer and Frieze [7] focused attention on locally tree-like graphs with large maximum degree, specifically Δ = Ω(log n) and girth g = Ω(log Δ).^{1} Under these assumptions, they proved O(n log n) mixing time of the Glauber dynamics when k > α_{0}Δ, where α_{0} ≈ 1.763. Molloy [18], under the same assumptions, proved the same conclusion when k > α_{1}Δ, where α_{1} ≈ 1.489. Very recently, Hayes [12] reduced the girth requirement in Molloy’s result to g ≥ 6.

All the aforementioned analyses of the Glauber dynamics use an approach known as the coupling method (see Sections 1.3 and 2.1), and more specifically a “maximal one-step coupling”. Molloy’s result seems to be the best possible using this approach; it appears that no one-step coupling, also known as a Markovian coupling, coalesces in polynomial time beyond Molloy’s threshold (see [18, Section 4]). In fact, Molloy raises the question of whether the constant α_{1} can be improved at all, and still have polynomial mixing time.

We give a positive answer, and in fact prove for all ϵ > 0 that k > (1 + ϵ)Δ suffices, assuming sufficiently large girth (11 suffices) and Δ = Ω(log n) (the implicit constant depends exponentially on 1/ϵ). Our proof uses a new coupling, defined with respect to the Cn-step evolution of the Glauber dynamics, for some C > 0 (where C also grows exponentially with 1/ϵ.). Our coupling is an example of a non-Markovian coupling of the Glauber dynamics. The non-Markovian aspect of our coupling appears to be essential. A non-Markovian coupling was previously used in a different context by Czumaj and Kutylowski [4] for the analysis of a Markov chain for generating a random permutation.

Here is the formal statement of our result.

Theorem 1. For every ϵ > 0, there exists C > 0 such that for every graph G on n vertices with maximum degree Δ ≥ C log n and girth g ≥ 11, and for every k ≥ (1 + ϵ)Δ, the Glauber dynamics for k-coloring G has mixing time at most Cn log n.

1The girth of a graph is the length of the shortest cycle.

Before presenting our results we state some related results that have appeared since the preliminary version of this paper. We continue the introduction with an informal exposition on the coupling technique along with its application in related previous work. We then briefly describe the intuition behind our improvement.

1.2 Recent Work

For k > 1.489Δ, Dyer et al. [8] reduced the degree requirement to a sufficiently large constant (that grows with k/Δ−1.489), and still assuming girth g ≥ 6.

There have been several works with small improvements in the girth requirements. Assuming k > 1.789Δ, Hayes and Vigoda [14] reduced the girth requirement to g ≥ 4 for Δ = Ω(log n), and this was further reduced to “locally sparse” graphs by Frieze and Vera [11]. For k > 1.489Δ, the girth requirement was recently reduced to g ≥ 5 by Lau and Molloy [16] for Δ = Ω(log^{3} n).

Finally, Hayes and Sinclair [13] have recently shown a lower bound of Ω(n log n) of the mixing time of the Glauber dynamics for constant degree graphs.

1.3 Coupling Idea for Previous Results

A coupling is simply a joint stochastic process (X_{t}, Y_{t}) on Ω × Ω. Our only requirement is that each of the processes (X_{t}) and (Y_{t}) viewed in isolation must be a Markov chain evolving with the same transition probabilities. No restrictions are placed on the correlations between the two chains, a feature essential to the power of the approach.

The goal is to design a coupling which minimizes the coalescence time, i.e., the smallest t such that X_{t} = Y_{t} with probability ≥ 1/2. The coalescence time from the worst pair of initial states is easily seen to be an upper bound on the mixing time (see Section 2.1). Despite several successes of this technique, (see e.g., [15, 17]) it is often an difficult task to design and analyze a coupling for all pairs of initial states.

The path coupling technique of Bubley and Dyer [2] is a useful tool for simplifying the coupling method. Roughly speaking, it suffices to define and analyze a coupling for only those initial pairs from a subset S ⊆ Ω^{2}, assuming the graph (Ω, S) is connected. This “partial coupling” is then extended to a coupling for an arbitrary pair of states. This approach has been instrumental in simplifying and improving results obtained via the coupling method (see e.g., [9, 20]).

In the setting of graph colorings, S is defined as the pairs of colorings which differ at exactly one vertex. To bound the coalescence time it suffices to define a joint evolution where a distance metric (such as Hamming distance) decreases in expectation.

A naive one-step coupling works when k > αΔ where α = 3. Consider a pair of states X_{t}, Y_{t} which only differ at vertex w, say X_{t}(w) = c_{X} and Y_{t}(w) = c_{Y}. The naive coupling chooses for both chains the same vertex v and color c for the attempted update. Observe that if v ∉ N(w) = {z ∈ V : (w, z) ∈ E)} or c ∉ {c_{Y} , c_{X}} then the attempted recoloring works or fails in both chains. Thus, there are at most 2Δ transitions which might increase the distance. Conversely, after any successful recoloring of w the two colorings are identical, and there are at least k − Δ such recolorings. For this coupling the condition k − Δ > 2Δ implies the Hamming distance decreases in expectation. Hence, we have O(n log n) coalescence time, and the same bound on the mixing time.

Jerrum [15] reduced α to 2 via a simple modification of the above coupling. First, choose a random vertex and color, say (v, c). If v ∈ N(w) and c ∈ {c_{Y} , c_{X}}, then set c′ = {c_{Y} , c_{X}} \ c. Otherwise, set c′ = c. Jerrum’s coupling attempts the recoloring (v, c) in X_{t} and (v, c′) in Y_{t}. There is now at most one coupled color pair per neighbor of w which might increase the distance (namely c = c_{Y}). For Jerrum’s coupling, the condition k − Δ > Δ implies O(n log n) mixing time of the Glauber dynamics. In fact, Jerrum’s analysis is tight for a worst pair of initial states.

Dyer and Frieze [7] avoid the worst-case scenario in Jerrum’s analysis by running the chains for a “burn-in period” before attempting the coupling. The burn-in period is sufficiently long for most vertices in the neighborhood of w to be recolored at least once. Assuming girth g = Ω(log log n), the color choices on the neighborhood of w will be roughly independent, as there is insufficient time for the dynamics to communicate the color choices along a path of length at least g. It then follows that the expected number of available colors for w is roughly k(1 − 1/k)^{Δ} ≈ k exp(−Δ/k). Further assuming Δ = Ω(log n), with high probability every vertex has close to its expected number of available colors for a polynomial number of transitions of the dynamics. It then suffices to have k exp(−Δ/k) > Δ, which reduces α to (approximately) 1.76322.

Molloy [18] further reduced α to 1.48908. In addition to the number of available colors, Molloy bounds the number of neighbors v of w which include two specific colors (e.g., c_{Y} and c_{X}) in X_{t}(N(v) \ {w}). Such a v can not be recolored to c_{X} or c_{Y} in either chain. Thus, under Jerrum’s coupling there are no transitions which cause v to differ in the two chains, i.e., v is “blocked” from the “bad” update in both chains.

In this paper we use the phrase “local uniformity” to refer, informally, to several propositions about graph colorings, all of which are true with high probability for random colorings, and so also for the Glauber dynamics, after sufficiently many steps. Section 5 states several of these results. The word “uniformity” refers to quantities which are about the same for all vertices of the graph, and/or all colors in [k]. It also refers to the fact that many of the same properties would hold for uniformly random color assignments in [k]^{V}, disregarding the requirement of being a proper coloring.

1.4 Our Approach

Our focus is on those updates which succeed in exactly one of the coupled chains, what we will call singly blocked updates. Under Jerrum’s coupling, this type of update always increases the Hamming distance. Roughly speaking, if we could create a coupling where updates always succeed in both chains or fail in both chains, we would eliminate half of these increases. This is exactly what we do. Let us examine these singly blocked updates in more detail.

We are interested in coupled updates of v ∈ N(w) which succeed in exactly one of the chains. Such a v has one of the colors, say c = c_{Y}, in its neighborhood N^{∗}(v) = N(v) \ {w}, but not c′ = c_{X}. In this scenario the attempted update of v to c_{Y} fails in X_{t} (i.e., it is blocked by some vertex in N^{∗}(v)), but the update of v to c_{X} succeeds in Y_{t}. Hence, the coupled (attempted) recoloring of v increases the Hamming distance. In the symmetric scenario where c = c_{X} and c′ = c_{Y}, the update of v succeeds in X_{t}, but fails in Y_{t}.

Our aim is to couple these “singly blocked” scenarios together. As a result, the attempted update of v (albeit to different colors in the two chains), will succeed in both chains or fail in both chains. Such a coupling necessitates having different colorings on the neighborhood N^{∗}(v). The high-level idea is to introduce temporary disagreements on two vertices, say z and z′, in N^{∗}(v). Vertex z will block the update of v in X_{t}, while z′ will block the update in Y_{t}. Surprisingly, we can guarantee that the temporary disagreements we create will disappear before their disagreement propagates. This requires examining the vertex-color choices at many future times. This is the crucially non-Markovian aspect of our coupling. In some sense we look into the future evolution to find a suitable z and z′, then revisit past decisions.

Here is a more precise (although still vague) picture of our non-Markovian coupling. Consider a pair of evolutions X_{0}, …, X_{T} and Y_{0}, …, Y_{T}, coupled under Jerrum’s coupling. Suppose these chains only differ at vertex w up until time t with X_{t}(w) = c_{X}, Y_{t}(w) = c_{Y}. At time t, under Jerrum’s coupling, we attempt to update v ∈ N^{∗}(w) to c_{Y} in X_{t} and c_{X} in Y_{t}, and there is a unique z ∈ N^{∗}(v) colored c_{Y}, but no z′ ∈ N^{∗}(w) colored c_{X}. We will modify the coloring on N^{∗}(w) in Y_{t} so that the attempted update fails in Y_{t} as well.

Let S(c_{X}) denote those z′ ∈ N^{∗}(v) whose current color can be replaced by c_{X} and such a change might only affect the update at time t. In other words, suppose at the last successful recoloring of z′ we had instead successfully updated z′ to c_{X}; if this modification does not affect the coloring of any neighbors in N^{∗}(z′) = N(z′) \ {v} at any time, then we include z′ in S(c_{X}). A vertex z′ ∈ S(c_{X}) can be used to block the attempted update in Y_{t} without direct “side effects.”

After the burn-in period, we have |S(c_{X})| ≈ |S(c_{Y})| with sufficiently high probability. We define a bijection (in fact, a “near-bijection”) between the set S(c_{X}) and the analogous set S(c_{Y}). Given z ∈ S(c_{Y}), the bijection defines an associated z′ ∈ S(c_{X}). We now modify the evolution of Y at earlier times, specifically at the previous updates of z′ and z. At the last (prior to time t) successful recoloring of z′ we still recolor it to X_{t}(z′) in X, but we recolor it to c_{X} in Y. Consequently, the attempted update of v at time t fails in both chains.

In order to ensure our partial coupling is valid, we make it “reversible”. This requires also modifying the last update of z in a reverse manner to z′. In particular, let S^{−1}(z′) denote those colors c for which z′ ∈ S(c). These are the colors which can be “swapped” with the current color of z′ and not affect the coloring on N^{∗}(z′). We define a bijection between the set S^{−1}(z′) and the analogous set S^{−1}(z). (This requires that we choose a z′ such that |S^{−1}(z′)| ≈ |S^{−1}(z)|.) Given the color of z′ at time t in X, the bijection defines a complementary color, say c, for z. We then perform the following modification of the evolution of Y. At the last (prior to time t) successful recoloring of z we still recolor it to c_{Y} in X, but we recolor it to c in Y.

We call such a sequence of modifications of the evolution of Y at earlier times a “non-Markovian update”. Our coupling evolves X for C_{pc}n steps where C_{pc} is a sufficiently large constant. We then evolve Y according to Jerrum’s coupling, applying non-Markovian updates whenever possible. These non-Markovian updates are defined to be symmetric with respect to the roles of X and Y. More precisely, if we take the final evolution of Y (after all non-Markovian updates were applied) and evolve X under our coupling, we obtain the original evolution of X. This reversibility of our coupling will imply it is a valid coupling.

1.5 Outline of the Paper

The following section presents background material on the coupling technique, and defines the basic element of our non-Markovian updates. Section 3 formally presents our partial coupling. We prove the coupling is a valid coupling in Section 4. Before analyzing the coupling in Section 6, we present some uniformity results in Section 5.

2 Preliminaries

We begin by defining the coupling technique and some Markov chain preliminaries. We then present the definitions which are our non-Markovian updates. We will let T_{pc} = C_{pc}n denote the length of our coupling. Thus, many of the following definitions will be a function of T_{pc}.

In the coupling over T_{pc} steps, we will not attempt any of our non-Markovian updates during the initial T_{m} steps. This additional burn-in period is needed to ensure that, for every vertex, most neighbors are recolored at least once. This is necessary to ensure that the neighborhoods of singly blocked vertices have the desired properties. We will set T_{m} = C_{m}n where C_{m} << C_{pc}.

2.1 Coupling Technique

Let Ω denote the states of the Glauber dynamics, P its transition matrix, and π its stationary distribution. For a pair of distributions μ and ν on Ω let d_{T V} (μ, ν) denote their (total) variation distance. The mixing time is defined as the number of steps until the Glauber dynamics is within variation distance 1/4 of π, starting from the worst initial state.

We use the coupling method to bound the mixing time. A t-step coupling is defined as follows. For every (X_{0}, Y_{0}) ∈ S, let (\overline{X}, \overline{Y}) = (\overline{X}_{(X_{0},Y_{0})}, \overline{Y}_{(X_{0},Y_{0})}) be a random variable taking values in Ω^{t} × Ω^{t}. We say (\overline{X}, \overline{Y}) is a valid coupling if for all (X_{0}, Y_{0}) ∈ Ω^{2}, and for all 0 < ℓ ≤ t, the distribution of X_{ℓ} is P^{ℓ}(X_{0}, ·) and the distribution of Y_{ℓ} is P^{ℓ}(Y_{0}, ·).

Every coupling satisfies the following bound, known as the Coupling Inequality [5] (or e.g., [1]). For all X_{0} ∈ Ω,

d_{T V} (P^{t}(X_{0}, ·), π) ≤ max_{Y_{0}∈Ω} Pr (X_{t} ≠ Y_{t} | X_{0}, Y_{0})

Therefore, by defining a t-step coupling where all initial pairs have coalesced (i.e., are at the same state) with probability at least 3/4, we have proved the mixing time is at most t.

For technical reasons, for a graph G = (V, E), we consider the Glauber dynamics defined on the set Ω = [k]^{V} where [k] = {1, …, k}. (This generalization of the dynamics to labellings occurs in all previous works [15, 20, 7, 18].) The definition of the dynamics is identical to the earlier definition. Observe that the stationary distribution of this new chain is uniformly distributed over proper colorings. Therefore, upper bounding the mixing time of this chain implies the same bound on the mixing time of the original chain defined only on proper colorings. The purpose of allowing improper colorings is to make it easier to “interpolate” between arbitrary legal colorings, a frequent operation in path coupling.

We will call the elements of Ω colorings, regardless of whether they are proper or not. We define a modified Hamming distance metric, ρ, on Ω as follows:

ρ(X, Y) := ∑_{w∈V : X(w)≠Y (w)} exp(d(w)/k).  (1)

Note that for regular graphs, ρ is equivalent to Hamming distance. In general, ρ gives a little more weight to vertices of higher degree.

2.2 Definitions

For X ∈ Ω, v ∈ V, denote the set of available colors for v in X by

A(X, v) := [k] \ X(N(v)).

Let X_{0}, …, X_{T_{pc}} be a sequence of colorings drawn from the Glauber dynamics, where the transitions X_{t} → X_{t+1} are defined by a sequence of uniformly random (vertex, color) pairs (v_{t}, c_{t}), for 1 ≤ t ≤ T_{pc}.

Definition 2. For any vertex v ∈ V, and time 1 ≤ t ≤ T_{pc}, we define the t-epoch for v, denoted I(v, t) = I_{X}(v, t), as the smallest time interval containing t, in which v is successfully recolored twice. In other words, I = (t_{v}, t̂_{v}), where t_{v} < t < t̂_{v}, and

t_{v} = max{1 ≤ t′ < t : v = v(t′), t′ ∈ T_{succ}}
t̂_{v} = min{T_{pc}, min{t′ > t : v = v(t′), t′ ∈ T_{succ}}},

where T_{succ} = {t : X_{t}(v(t)) = c(t)} denotes the set of successful update times. If v has not been successfully recolored at some time prior to t, then we consider t_{v} and I(v, t) to be undefined.

We next lay down a set of eligibility criteria which must be met in order for a vertex to be considered for a non-Markovian update. Although they are technical, we need them to ensure that our coupling is well-defined.

For each 0 ≤ t ≤ T_{pc}, let U_{t} be a rooted subtree of G. In our construction, U_{t} will be a tree rooted at the initial disagreement, which contains all potential disagreements up to time t.

Definition 3. Fix a time t ∈ [1, T_{pc}]. For a vertex z ∈ U_{t} and a color c, we say “c is an swappable color for z at time t” if all of the following hold:

1. I(z, t) ⊆ [t − T_{m}, t + T_{m}], where T_{m} = C_{m}n for a constant C_{m} which will be specified later.

2. c ∈ A(X_{t}, z).

3. No child of z attempts color c (successfully or not) at any time in I(z, t).

In our application, the children of z will always be leaves of U_{t}.

Definition 4. Let 1 ≤ t ≤ T_{pc}, let c, c′ ∈ [k], and let w be a non-leaf node of U_{t}. If exactly one of c and c′ appears among the colors assigned to children of w under X_{t}, then we say w is singly blocked for colors c, c′ at time t. (For our application, c and c′ will be the colors of a disagreement at the parent of w.)

The following definition is the central component of our non-Markovian updates.

Definition 5. Suppose w is singly blocked for colors c_{b}, c_{u} at time t. Let B = {b_{1}, …, b_{ℓ}} ≠ ∅ denote the set of children of w receiving color c_{b}. Thus, c_{b} is the blocked color and c_{u} is the color that does not appear on a child of w.

Let A = {a_{1}, …, a_{j}} be the union of B and those children of w with color c_{b} swappable, sorted in decreasing order of how many swappable colors each has (ties broken lexicographically). Similarly, let Â = {â_{1}, …, â_{j′}} be the children of w that have color c_{u} swappable, ordered in the same manner. Let m = min{j, j′}.

Define the complementary blockers U as follows. If i ≤ m for all a_{i} ∈ B, then set

U = {â_{i} : a_{i} ∈ A}

Otherwise, if i > m for some a_{i} ∈ B, then U is undefined.

For each â_{i} ∈ U, let Ĉ be the union of X_{t}(â_{i}) and the set of swappable colors for â_{i}. Let C be the set of swappable colors for a_{i}. Lexicographically sort Ĉ = {ĉ_{1} < ⋯ < ĉ_{α′}} and C = {c_{1} < ⋯ < c_{α}}. Let ĉ_{β} = X_{t}(â_{i}). If β ≤ m, then the complementary color for a_{i} is c_{β}. Otherwise, the complementary color is undefined. If the complementary blockers and all the complementary colors are defined, then we say w is swap-eligible at time t.

In the construction of our coupling, we will be especially concerned with the possible propagation of disagreements when such a singly blocked vertex w is updated to c_{b} or c_{u} at time t. When w is swap-eligible and singly blocked for c_{b} under X_{t}, we will ensure that w is singly blocked for c_{u} under Y_{t}. To do this, we will ensure that Y_{t}(U) = c_{u}, and, for each a_{i} ∈ B, Y_{t}(a_{i}) equals the complementary color for a_{i}. In the case when c_{t} = c_{b}, this coupling will save a disagreement, compared with the greedy one-step coupling (when c_{t} = c_{u}, the disagreement still propagates).

Our final definition captures the generalization of the Glauber dynamics needed for our application of the path coupling technique in the proof of our main theorem. In the proof we will consider an arbitrary pair of colorings Q_{0}, Q′_{0}. We will then run these chains independently for T_{b} steps. Label the vertex set as V = {1, 2, …, n}. Then for all 1 < i ≤ n, we will set A_{i} = {i, i + 1, …, n}, and for all 0 ≤ t ≤ T_{b} we define W_{t}^{i} to be the same as Q_{t} on A_{i} and the same as Q′_{t} on V \ A_{i}.

Note, Q_{t}, W_{t}^{1}, …, W_{t}^{n}, Q′_{t} is a sequence of colorings where successive colorings only differ on (at most) one vertex. Thus, we can use this sequence as the path in our application of the path coupling technique. For a specific i, the sequence W_{0}^{i}, …, W_{T_{b}}^{i} does not evolve according to the Glauber dynamics. But the final coloring W_{T_{b}}^{i} will still have the important local uniformity properties that Q_{T_{b}} and Q′_{T_{b}} also have. Thus, we call it a T_{b}-step evolution of the generalized Glauber dynamics. Here is the precise definition of the generalized Glauber dynamics.

Definition 6. Let A ⊆ V and 0 ≤ t ≤ T. Let Q_{0}, …, Q_{t} and Q′_{0}, …, Q′_{t} be sequences of random colorings distributed according to Glauber dynamics, with an arbitrary coupling that preserves the vertex sequence v(1), …, v(t) (and Q_{0}, Q′_{0} are arbitrary). Define a chain of colorings W_{0}, …, W_{T} as follows. The colorings W_{0}, …, W_{t} are defined by the following interpolation rule: for every i ≤ t, w ∈ V, set

W_{i}(w) = \{ \begin{matrix}Q_{i}(w) & if w ∈ A \\ Q′_{i}(w) & otherwise \end{matrix}

The remainder of the evolution, W_{t+1} …, W_{T} is sampled according to Glauber dynamics on (not necessarily proper) k-colorings of G, starting at W_{t}. We call any such chain of colorings W_{0}, …, W_{T}, a T -step generalized Glauber dynamics.

3 Coupling Construction

Our coupling works by taking an arbitrary pair of colorings Q_{0}, Q′_{0} and running them independently for T_{b} steps where T_{b} = O(n log n). This burn-in period of T_{b} steps will ensure that with high probability the neighborhood of every vertex looks close to random in both Q_{T_{b}} and Q′_{T_{b}}. We then apply path coupling to Q_{T_{b}} and Q′_{T_{b}}. Thus, we define a sequence of colorings W_{0}^{0} = Q_{T_{b}}, W_{0}^{1}, ..., W_{0}^{ℓ} = Q′_{T_{b}} where W_{0}^{i} and W_{0}^{i+1} only differ on a single vertex. Now for each pair W_{0}^{i}, W_{0}^{i+1} we define and analyze a coupling over T_{pc} steps whose distance decreases in expectation. Each of these intermediate colorings W_{0}^{i} is an “interpolation” between Q_{T_{b}} and Q′_{T_{b}}. More precisely, it corresponds to a coloring generated by T_{b} steps of the generalized Glauber dynamics.

Thus, our coupling lemma will consider a pair of colorings X_{0} = W_{0}^{i} and Y_{0} = W_{0}^{i+1} which differ at a single vertex and were generated by T_{b} steps of the generalized Glauber dynamics. We will then define a T_{pc} step coupling of X_{0} and Y_{0} which, in expectation, decreases their distance. After using this coupling to define Q_{T_{b}+T_{pc}}, Q′_{T_{b}+T_{pc}}, we repeat the above procedure of interpolation and applying our T_{pc} step coupling. After O(log n) repetitions of this kind, the chains will have coalesced with probability approaching 1.

Lemma 7. For every ϵ > 0, there exist C_{d}, C_{pc}, C_{b} such that for every graph G on n vertices of maximum degree Δ, and girth g ≥ 11, and for every k ≥ max{(1 + ϵ)Δ, C_{d} log n}, there exists a T_{pc} = C_{pc}n-step partial coupling of Glauber dynamics, defined for all pairs of colorings which differ at a single vertex, with the following property. Sample X_{0} = Z_{T} according to a T - step generalized Glauber distribution, where T ≥ T_{b} = C_{b}n log n. Arbitrarily choose Y_{0} which disagrees with X_{0} at a single vertex. Then with probability ≥ 1 − n^{−10} (over the random choice of X_{0}),

E (ρ(X_{T_{pc}}, Y_{T_{pc}}) | X_{0}, Y_{0}) < \frac{1}{2}ρ(X_{0}, Y_{0}).

where X_{0}, …, X_{T_{pc}}, Y_{0}, …, Y_{T_{pc}} are generated according to our partial coupling.

3.1 The Dominating Chain

The coupling we will construct is perhaps most easily viewed as a function Ψ_{X_{0},Y_{0}} : (V × [k])^{T_{pc}} → (V × [k])^{T_{pc}}, which maps each sequence of (vertex, color) choices for the (X_{t}) chain to a corresponding sequence of choices for the (Y_{t}) chain. For such a function to be a coupling, it must be one-to-one.

To ensure our non-Markovian updates are one-to-one, we first need to guarantee that the coupling has certain properties. For example, given X_{0} and Y_{0} initially differ on a vertex v, we need to ensure this disagreement spreads in a locally tree-like manner. To do this, we will employ a simple Markov chain Z_{0}, …, Z_{T_{pc}}, whose state space is the set of functions Z : V → 2^{[k]}. We call (Z_{t}) the dominating chain, because it will satisfy, for every w ∈ V, 0 ≤ t ≤ T_{pc},

X_{t}(w) ⊆ Z_{t}(w),

and for all w ∈ V, 0 ≤ t ≤ T_{pc} where X_{t}(w) ≠ Y_{t}(w),

{X_{t}(w), Y_{t}(w)} ⊆ Z_{t}(w)

Definition 8. Let X_{0}, Y_{0} differ at a single vertex v, and denote a sequence of (vertex, color) updates by s = ((v_{1}, c_{1}), …, (v_{T_{pc}}, c_{T_{pc}})) ∈ (V × [k])^{T_{pc}}. We define the initial set Z_{0} by, for every w ∈ V,

Z_{0}(w) = {X_{0}(w), Y_{0}(w)}.

Note that, initially, |Z_{0}(w)| > 1 only for w = v. For each t ≥ 1, if v_{t} has any neighbor w such that |Z_{t−1}(w)| > 1 and c_{t} ∈ Z_{t−1}(w), then we set

Z_{t}(v_{t}) = Z_{t−1}(v_{t}) ∪ {c_{t}}.

Otherwise, if c_{t} ∉ ⋃_{w∼v} Z_{t−1}(w), we update

Z_{t}(v_{t}) = {c_{t}}.

Otherwise, Z_{t}(v_{t}) = Z_{t−1}(v). For all w ≠ v_{t}, Z_{t}(w) = Z_{t−1}(w).

Finally, let D_{t} = {w ∈ V : |Z_{t}(w)| > 1}, and let D = D_{≤T} be the union of these.

3.2 Construction

Fix initial colorings X_{0}, Y_{0}. The basic idea is to define a sequence of couplings Ψ^{0}, …, Ψ^{T}, starting with Ψ^{0} = id, where Ψ^{i} is defined inductively in terms of Ψ^{i−1} by a number of “partner swaps.” In other words, for each i, there will be some pairs of color sequences c^{0} and ĉ for which we will set

Ψ^{i}(c^{0}) = Ψ^{i−1}(ĉ) and Ψ^{i}(ĉ) = Ψ^{i−1}(c^{0}).

More precisely, there is a permutation π = π^{i} of order 2 (or 1), such that Ψ^{i} = Ψ^{i−1} ∘ π, i.e., ĉ = π(c^{0}). Since the composition of one-to-one functions is one-to-one, this will imply that Ψ^{T} is, in fact, a valid coupling. We still need to define the mappings π.

The coupling Ψ^{i} will differ from Ψ^{i−1} on color choices relevant to the attempted update at time i. In particular, typically Ψ^{i} and Ψ^{i−1} will either be identical, or differ only on the color choice at time i. However, when we attempt a non-Markovian update at time i, we will also modify color choices at other times. A non-Markovian update requires that the blocking neighbors of v_{t} have each been recolored at least once; otherwise, v_{t} is not swap eligible (see Definition 5). For this reason, we will only consider making our non-Markovian updates after at least T_{m} steps have occurred. Therefore, we will set Ψ^{1}, …, Ψ^{T_{m}} equal to Ψ^{0} = id. For i > T_{m}, we will define Ψ^{i} inductively.

Coupling Definition

Choose c^{0} randomly from ([k] × V)^{T}. This defines the T -step evolution for X_{0}. We will define the coupled evolution for Y_{0} inductively, where Ψ^{i} will denote the coupling in stage i, and Ψ^{T} will be the final coupled evolution for Y_{0}.

Let c^{0} = ((v_{1}, c_{1}^{0}), …, (v_{T} , c_{T}^{0} )). The i-th coupling will be denoted as c^{i} = Ψ^{i}(c^{0}) and c^{i} = ((v_{1}, c_{1}^{i}), …, (v_{T} , c_{T}^{i})). Thus, all couplings will use the same vertex selections and will only differ on the attempted new color choice. Hence, we will ignore the vertex choice, and denote c^{i} = (c_{1}^{i}, …, c_{T}^{i}).

First, work out the entire evolution of the dominating chain. If either of the following occurs for D, then let Ψ^{T} = id:

Completing a cycle: D is within 4 edges of completing a cycle.

Repropagation: There exist times t′ < t such that

1. v_{t} ∈ D_{t′}, and

2. there exists w ∈ N(v_{t}) such that |Z_{t−1}(w)| > 1 and c_{t}^{0} ∈ Z_{t−1}(w).

(Condition 2 would cause v_{t} to be added to D at step t, except it had already been added by time t′.)

Otherwise, we say D is “well-behaved”, and we define our coupling by the following inductive procedure. Note that the conditions for D being wellbehaved ensure that if an attempted color c_{t}^{0} matches a disagree neighbor p ∈ N(v_{t}) (in particular, X_{t}(p) ≠ Y_{t}(p) and c_{t}^{0} ∈ {X_{t}(p), Y_{t}(p)}), then p is the unique disagree neighbor of v_{t}. Thus, the disagreements propagate along an implicit tree.

Our initial couplings Ψ^{0}, Ψ^{1}, …, Ψ^{T_{m}} are each the identity coupling. In what follows, we assume i > T_{m}.

Given Ψ^{i−1}, we construct Ψ^{i} by defining a permutation π on [k]^{T} and setting Ψ^{i}(c^{0}) = Ψ^{i−1}(π(c^{0})). For convenience, we let ĉ = π(c^{0}).

Suppose Ψ^{i−1} is given. Work out the T -step evolution of Y_{0} defined by Ψ^{i−1}(c^{0}). Denote this evolution as Y^{i−1}. Define ĉ_{i} as follows:

• If X_{i}(p) ≠ Y_{i}(p) for some p ∈ N(v_{i}) and c_{i}^{0} = X_{i}(p), let ĉ_{i} = Y_{i}^{i−1}(p).

• If X_{i}(p) ≠ Y_{i}(p) for some p ∈ N(v_{i}) and c_{i}^{0} = Y_{i}^{i−1}(p), let ĉ_{i} = X_{i}(p).

• Otherwise, let ĉ_{i} = c_{i}^{0}.

Furthermore, if case (1) or (2) holds and v_{i} is singly-blocked in X for colors X_{i}(p), Y_{i}^{i−1}(p), and v_{i} is swap-eligible, then modify the following updates:

1. Let c_{b} ∈ {X_{i}(p), Y_{i}^{i−1}(p)} denote the blocking color, and c_{u} denote the unblocked color. Let B = {b_{1}, …, b_{ℓ}} ⊂ N(v_{i}) denote those neighbors with the blocking color in X_{i}. Let U = {u_{1}, …, u_{ℓ}} ⊂ N(v_{i}) denote their complementary neighbors, and {β_{1}, …, β_{ℓ}} denote the complementary colors.

2. For b_{j} ∈ B,

(a) Let t be the last successful recoloring of b_{j} in X prior to time i. Set ĉ_{t} = β_{j}.

(b) For any time t ∈ Epoch_{i}^{X}(b_{j}) where v_{t} ∈ N(b_{j}) and c_{t}^{0} = X_{i}(b_{j}), set ĉ_{t} = β_{j}.

3. For u_{j} ∈ U,

(a) Let t be the last successful recoloring of u_{j} in X prior to time i. Set ĉ_{t} = c_{u}.

(b) For any time t ∈ Epoch_{i}^{X}(u_{j}) where v_{t} ∈ N(u_{j}) and c_{t}^{0} = Y_{i}^{i−1}(u_{j}), set ĉ_{t} = c_{u}.

Except for the changes above (if any), keep the rest of ĉ the same as c^{0}.

4 Validity

We will consider the evolution of the chain for several sequences of updates. These sequences will always attempt to recolor vertex v_{t} at time t, and will only differ on their attempted new color. Therefore, we omit the vertex choice, and for σ = (c_{1}, …, c_{T}), we let X_{t}^{σ} denote the evolution defined by σ, starting at X_{0}. Let c^{0} = (c_{1}^{0}, …, c_{T}^{0} ) denote the initial evolution of X_{0}, and let c^{i} = (c_{1}^{i}, …, c_{T}^{i}) = Ψ^{i}(c^{0}) denote the i-th coupling. When σ is dropped, we are implicity referring to the evolution defined by c^{0}.

Observation 9. For all z, t, σ, X_{t}^{σ}(z) ∈ Z_{t}^{σ}(z). Hence, if |Z_{t}^{σ}(z)| = 1, then X_{t}^{σ}(z) = Z_{t}^{σ}(z).

We begin with a few definitions. Let D_{t}^{σ} = {w : |Z_{t}^{i}(w)| > 1}, and let D = ∪_{t}D_{t}. Also, let Epoch_{t}^{σ}(z) denote the interval from the last successful recoloring of z (under driving sequence σ, starting from X_{0}) prior to (or equal to) t (0 if none), to the first one after t (T if none). Let S_{t}^{σ}(w) denote the set of swappable colors for vertex w at time t for the evolution defined by updates c^{0}, starting at X_{0}.

We will primarily be interested in the evolution from X_{0} for sequences c^{0} and ĉ, hence we can simplify notation by letting X_{t} = X_{t}^{c^{0}}, Z_{t} = Z_{t}^{c^{0}}, Epoch_{t} =

Epoch_{t}^{c^{0}}, S_{t} = S_{t}^{c^{0}}, and letting X̂_{t} = Xĉ ; t, Ẑ_{t} = Zĉ ; t. Similary, let Y_{t}^{i} = Y_{t}^{Ψ^{i}(c^{0})}

and Ŷ_{t}^{i} = Ŷ_{t}^{Ψ^{i}(ĉ)}.

Our proof will consider the pair of sequences c^{0}, ĉ from round i of the construction. These sequences might differ at time i and possibly by an appropriate interchange of colors on some subset W of neighbors of v_{i}, due to our non-Markovian swap. The following definition formalizes the necessary notion of similar sequences. On an initial reading, one can consider W = ∅, and then the sequences only differ on their attempted recoloring of v_{i}.

Definition 10. We call an ordered pair of color sequences c^{0}, ĉ swappable if there exists a time i and a subset of vertices W ⊂ N(v_{i}) \ D, such that the following hold:

1. D is well-behaved (at least 4 edges away from completing a cycle).

2. N(v_{t}) ∩ D_{i} = {p}.

3. c_{i}^{0}, ĉ_{i} ∈ Z_{i}(p);

4. Let w ∈ W, and let t be the last successful recoloring time of w in X prior to time i. Define

α_{w} = c_{t}^{0}, and α̂_{w} = ĉ_{t}.

We require that t > 0, α_{w} ≠ α̂_{w} and α̂ ∉ X_{t}(N(w)). Thus, α̂_{w} and α_{w} are both valid updates for w in X_{t}.

5. For all w ∈ W, all times t ∈ Epoch_{i}(w) such that t ≠ i and v_{t} ∈ N(w), we require that

(a) c_{t}^{0} ≠ α̂_{w} and ĉ_{t} ≠ α_{w}, and

(b) c_{t}^{0} = α_{w} if and only if ĉ_{t} = α̂_{w}, (c) if v_{t} = v_{i}, then c_{t}^{0} ≠ α_{w}, ĉ_{t} ≠ α̂_{w}

In other words, during Epoch_{i}(w), color α̂_{w} is a swappable color for w, and we are interchanging α_{w} with α̂_{w}.

6. At all other times t, c_{t}^{0} = ĉ_{t}.

It is worth pointing out the purpose of the conditions in (5). Part (a) will imply that α̂_{w} is a swappable color for w in X, while α_{w} is a swappable color for w in X̂; (ii) will imply these coupled updates are blocked by w in both chains, and the difference at w won’t propagate, and (iii) eliminates any direct interactions (via v_{i}) between vertices in W.

The next claim captures the essential properties of swappable sequences which will be used in our proof that our coupling is valid.

Claim 11. For a pair of swappable sequences c^{0}, ĉ with respect to time i, W ⊂ N(v_{t}), the following hold:

1. D^{c^{0}} = Dĉ

2. The following pairs are identical on V \ W:

Z_{i} and Ẑ_{i}, X_{i} and X̂_{i}, Y_{i} and Ŷ_{i}.

3. For w ∈ W, X_{i}(w) = α_{w}, and X̂_{i}(w) = α̂_{w}

4. For w ∈ W,

\begin{matrix}α̂_{w} ∈ S_{i}(w) and α_{w} ∈ Ŝ_{i}(w) \\ α_{w} ∈ S_{i}(w) ⟺ α̂_{w} ∈ Ŝ_{i}(w) \end{matrix}

5. For y ∈ N(v_{i}) \ D,

|S_{i}(y)| = |Ŝ_{i}(y)|

We defer the proof of the claim until the end of the section. We are now prepared to prove our main lemma that our coupling is valid.

Lemma 12. For 1 ≤ i ≤ T, Ψ^{i} is a valid coupling (one-to-one).

Remark 13. Recall, our definition of Ψ^{i} constructs a function π = π^{i} : [k]^{T} → [k]^{T} and sets Ψ^{i} = Ψ^{i−1} ∘ π. In the coupling definition, π(c^{0}) = ĉ. The key to our proof is that π is a permutation. This then implies Ψ^{i} is a oneto-one function by induction, since Ψ^{0} is the identity, and the composition of one-to-one functions is also one-to-one. Our proof that π is a permutation will be simplified by the fact that it is of order 1 or 2, and it respects the subcases (A), (B), (C) (which partition [k]^{T}) in the proof below. In other words, whenever c ∈ [k]^{T} falls into case, say, (B), in step i, it will also be the case that ĉ = π(c^{0}) falls into the same case in step i, and that π(ĉ) = c^{0} (i.e., π(π(c^{0})) = c^{0}). Note that these properties imply that π is one-to-one. Also note that these properties can be verified for all c^{0} in case (B) without even knowing the definition of π for the other cases. This allows us to analyze π one case at a time.

Proof of Lemma 12. Suppose D has a near-loop or repropagation.

In this case Ψ(c^{0}) = Ψ^{T} (c^{0}) = c^{0} and it is clear that Ψ is one-to-one for sequences falling into this case.

For the remaining cases, D is well-behaved. We induct on i, following the outline in Remark 13.

(A) No change, i.e., ĉ = c^{0} and Ψ^{i}(c^{0}) = Ψ^{i−1}(c^{0}): Then it follows by induction.

If c_{i}^{0} ∈ Z_{i}(N(v_{i}) ∩ D_{i}) then |D_{i} ∩ N(v_{i})| = 1, otherwise D is not “wellbehaved”. Let {p} = D_{i} ∩ N(v_{i}). Let δ_{1} = X_{i−1}(p), δ_{2} = Y_{i−1}^{i−1}(p). Recall, in the coupling construction, in this case we are choosing the color of a parent disagreement. Thus, c_{i}^{0} ∈ {δ_{1}, δ_{2}}. We divide the analysis into two further cases, either: (B) both or neither of the colors δ_{1}, δ_{2} appears in N(v_{i}) \ {p}; or (C) exactly one of the colors δ_{1}, δ_{2} appears in N(v_{i}) \ {p}.

(B) Suppose one of the following holds:

[doubly-blocked]  δ_{1}, δ_{2} ∈ X_{i}(N(v_{i}) \ {p}), or
[unblocked]  δ_{1}, δ_{2} ∉ X_{i}(N(v_{i}) \ {p}).

Note, ĉ_{i} = {δ_{1}, δ_{2}} \ c_{i}^{0}, and

ĉ = (c_{1}^{0}, ..., c_{i−1}^{0}, ĉ_{i}, c_{i+1}^{0}, ..., c_{T}^{0} ).

which differs from the original driving evolution at time i. By Claim 11, part 2, ĉ also falls into this case. Then it is clear that the corresponding sequence for ĉ is π(ĉ) = c^{0}. This completes the proof for this case.

(C) Suppose the following holds:

[singly-blocked]  δ_{1} ∈ Z_{i}(N(v_{i}) \ {p}), δ_{2} ∉ Z_{i}(N(v_{i}) \ {p}), or
[singly-blocked]  δ_{2} ∈ Z_{i}(N(v_{i}) \ {p}), δ_{1} ∉ Z_{i}(N(v_{i}) \ {p}).

As in the last case, note, ĉ_{i} = {δ_{1}, δ_{2}} \ c_{i}^{0}. The sequences c^{0} and ĉ = π(c^{0}) also differ on a set of times depending on the singly-blocking set. Denote the blocking color by c_{b} ∈ {δ_{1}, δ_{2}}, and the unblocked color as c_{u} = {α, β} \ {c_{b}}.

Now consider the non-Markovian updates where c^{0} and ĉ differ. Let B = {b_{1}, ..., b_{ℓ}} denote the blocking neighbors of v_{i}, and U = {u_{1}, ..., u_{ℓ}} denote their corresponding neighbors. Also, let {β_{1}, ..., β_{ℓ}} denote the complementary colors of B, and {γ_{1}, …, γ_{ℓ}} the current colors of U, i.e., X_{i}(u_{j}) = γ_{j}.

The sequences c^{0}, ĉ are swappable sequences with respect to time i where W = B ∪ U, and the auxillary colors α_{w}, α̂_{w} for w ∈ W are as follows:

\begin{matrix}For b_{j} ∈ B, α_{b_{j}} = c_{b}, α̂_{b_{j}} = β_{j}, \\ For u_{j} ∈ U, α_{u_{j}} = γ_{j}, α̂_{u_{j}} = c_{u}, \end{matrix}

Using Claim 11,part 3, we can observe the effect of the altered color choices for B ∪ U. For all u ∈ U,

X̂_{i}(u) = c_{u},

and, for all b_{j} ∈ B,

X̂_{i}(b_{j}) = β_{j}

Combined with Claim 11, part 2, we then have that ĉfalls into the same case, where v_{i} is blocked (by the set U) for color c_{u}, and unblocked for color c_{b}.

By Claim 11, part 5, for all y ∈ N(v_{i}) \ D,

|S_{i}^{c^{0}}(y)| = |Sĉ ; i(y)|

Hence, when we order the neighbors of v_{i} (excluding D) by the number of swappable colors, it is the same ordering for X and X̂, i.e., in X̂ the complementary neighbor of u_{j} ∈ U is b_{j}. Moreover, by part 4 of Claim 11, the pairing between Ŝ(u_{j}) ∪ {β_{j}} and Ŝ(b_{j}), is the same as the pairing between S(u_{j}) and S(b_{j}) ∪ {γ_{j}}. Hence, in X̂, γ_{j} is the complementary color of β_{j}.

Therefore, when we apply the non-Markovian updates to ĉ, we end up with c^{0}. In other words, π(ĉ) = c^{0}, which completes the proof in this case.

It remains to prove Claim 11. The claim will follow easily from the following claim detailing the evolution of the dominating chain under c^{0} versus ĉ.

Claim 14. Consider a pair of swappable sequences c^{0}, ĉ (with respect to time i). The following hold:

1. For all y ∉ W, all t, Z_{t}(y) = Ẑ_{t}(y);

2. For all w ∈ W, all t ∉ Epoch_{i}(w), Z_{t}(w) = Ẑ_{t}(w);

3. For all w ∈ W, all t ∈ Epoch_{i}(w), Z_{t}(w) = {α_{w}}, and Ẑ_{t}(w) = {α̂_{w}} .

Proof of Claim 14. The proof is by induction on t (the base case t = 0 is immediate). We’ll consider three cases:

v_{t} = w ∈ W: Note, N(w) ∩ W = ∅ by the girth assumptions. Hence, by (1), for all y ∈ N(w), Z_{t}(y) = Ẑ(y). Recall that if |Z_{t}(y)| = 1 then X_{t}(y) = Z_{t}(y), and similarly for Ẑ and X̂. Thus, for all y ∈ N(w) \ D, we now have that X_{t}(y) = X̂(y). Since N(w) ∩ D = {v_{i}}, and v_{i} first disagrees at time i, then for all t′ < i we have |Z_{t′}(v_{i})| = 1 and, for all y ∈ N(w), X_{t}(y) = X̂(y).

There are two subcases to consider, either: (a) t is the last successful recoloring, in X, of w prior to time i, and c_{t}^{0} = α_{w}, ĉ_{t} = α̂_{w}, or (b) c_{t}^{0} = ĉ_{t}.

In case (a), t < i and by the above observations, we know that X and X̂ are identical on the neighborhood of w at time t. By definition neither α_{w} or β_{w} appear in the neighborhood of w in X_{t}, and hence in X̂_{t} as well. Therefore the update succeeds in X_{t} and X̂_{t}, and henceforth (3) applies.

In case (b), by (1) the neighborhood of w is identical in Z_{t} and Ẑ_{t} and thus the update has the same effect in both chains.

v_{t} ∈ N(w) for some w ∈ W: Suppose t ∉ Epoch_{i}(w). Then c_{t}^{0} = ĉ_{t}. By (1) and (2) the neighborhood of v_{t} is identical in Z_{t} and Ẑ_{t}, and hence the update has the same effect in both chains, and (1) still applies to v_{t} after the update.

Consider if t ∈ Epoch_{i}(w). Now (1) and (3) apply. Note, either: (a) c_{t}^{0} = ĉ_{t} and c_{t}^{0} ∉ {α_{w}, α̂_{w}}, or (b) c_{t}^{0} = α_{w}, ĉ_{t} = α̂_{w}. In (a), by (3), w plays no role. Moreover, by (1), Z, Ẑ are identical on N(v_{t}) \ {w}. Hence the update has the same effect in both chains. In (b), by (3), the update is blocked by w in both chains.

Otherwise: In the remaining cases, c_{t}^{0} = ĉ_{t}, v_{t} ∉ W, N(v_{t}) ∩ W = ∅, so by (1), the neighborhood of v_{t} is identical in Z and Ẑ. And, once again, the update has the same effect in the two chains.

Proof of Claim 11. We prove the statements in order.

Note W ∩ D^{c^{0}} = ∅. Hence, for all w ∈ W, all t, |Z_{t}(w)| = 1. Then by parts 2 and 3 of Claim 14, |Ẑ_{t}(w)| = 1, hence W ∩ Dĉ = ∅. Then, by part 1 of Claim 14, we have that D^{c^{0}} = Dĉ.

For part (2) of the claim, the statement of Z and Ẑ is implied by Claim 14 and part (1) of this claim. To prove the statement for X and X̂, note, by (1) in Claim 14 and observation 9, we have that for all y ∈ V \ (D ∪ W), for all t ≤ i, X_{t}(y) = X̂_{t}(y). Using this, we will also prove that for all t ≤ i, X_{t} and X̂_{t} are identical on D. The proof is by induction. The base case t = 0 is immediate. Consider an update of v_{t} ∈ D. Its neighborhood can only differ on N(v_{t}) ∩ W. But v_{i} is the only vertex in D with neighbors in W. Hence, for t < i the neighborhood of v_{t} is identical in X and X̂, and both chains attempt the same new color. Hence, the update succeeds or fails in both.

Now we will prove that Y_{i} and Ŷ_{i} are identical on V \ W. Note, the set W and its neighbors play no role in the coupling before time i. And, c^{0}, ĉ are identical on V \ W, except for v_{i} ∈ D. Since X_{t} and X̂_{t} are identical on V \ W for t < i, the couplings for c^{0} and ĉ evolve the same for all t < i.

Statement (3) of the claim follows immediately from part 3 of Claim 14, and part 1 of this claim.

For part 4, since W ∩D = ∅, for t ∉ Epoch_{i}(w), w ∈ W, Z_{t}(w) = X_{t}(w) = X̂_{t}(w) = Ẑ_{t}(w). Hence, Epoch_{i}^{c^{0}}(w) = Epochĉ ; i(w). By the definition of swappable sequences, during this epoch, we know there are no attempted recolorings of neighbors of w to α̂_{w} in c^{0} and to α_{w} in ĉ. Hence, α̂_{w} is a swappable color in X for w in this epoch, and α_{w} is a swappable color in X̂ for w. Moreover, since attempted recolorings of neighbors of w to α_{w} in c^{0} correspond to attempted recolorings to α̂_{w} in ĉ, we have the second statement in part (4) of this claim.

For y ∈ N(v_{i}) \ (D ∪ W), since N(y) ∩ D = {v_{i}}, they and their neighborhood excluding v_{i} are identical at all times. Hence, their swappable colors are the same in X and X̂. For w ∈ W, for any color c′ ∉ {α_{w}, α̂_{w}},

c ∈ S_{i}(w) ⟺ c ∈ Ŝ_{i}(w).

Combined with part 4 of the claim, we have that |S_{i}(w)| = |Ŝ_{i}(w)|. This completes the proof of the claim.

5 Local Uniformity Properties

In order to prove our main theorem, we require several “local uniformity” properties of random k-colorings, which are key to showing that our partial coupling decreases Hamming distance in expectation. After a “burn-in” period of O(n log n) steps, colorings generated by a generalized Glauber dynamics will satisfy these properties locally, with high probability.

This approach was introduced by Dyer and Frieze [7], and subsequently refined by Molloy [18] and Hayes [12].

The following theorem of [12] establishes two properties of random colorings, each of which holds with high probability for the Glauber dynamics after O(n log n) steps “burn-in”. We will use these properties to bound the probability of certain “bad” events, which inhibit the convergence of our coupling.

Fix a vertex v, and a subset S ⊂ N(v). For every color c, i ≥ 0, and coloring X, let S_{c,i}(X) denote the set of w ∈ S such that exactly i neighbors z of w, excluding v, satisfy X(z) = c. We call this the subset of S which is “i times blocked for c.”

Theorem 15. If g ≥ 6 then for all v ∈ V and t ≥ Cn,

Pr (||A(X_{t}, v)| − ke^{−d(v)/k}| > δk) ≤ e^{−Cδ^{2}k}.  (2)

Moreover, for every S ⊂ N(v), c_{1} ≠ c_{2} ∈ [k], non-negative integers i_{1}, i_{2}, and t ≥ Cn log Δ,

Pr (||S_{c_{1},i_{1}}(X_{t}) ∩ S_{c_{2},i_{2}}(X_{t})| − \frac{1}{i_{1}!i_{2}!} ∑_{w∈S} e^{−2d(w)/k} (\frac{d(w)}{k})^{i_{1}+i_{2}} | > δΔ)
≤ e^{−Cδ^{2}Δ}. (3)

Remark 16. Although concentration inequality (3) may look ghastly, the point is that the distribution of |S_{c_{1},i_{1}}(X_{t}) ∩ S_{c_{2},i_{2}}(X_{t})| is concentrated at a value which depends only on S, i_{1} and i_{2}, not on the colors c_{1} and c_{2}.

Note that the case when S = N(v) and i_{1} = i_{2} = 0 corresponds to the local uniformity property of Molloy [18] (originally proved under the stronger assumption k/Δ > \sqrt{2}).

Also note that if we fix S, i_{1}, and apply (3) for each 0 ≤ i_{2} ≤ Δ, we can conclude

Pr (||S_{c_{1},i_{1}}(X_{t})| − \frac{1}{i_{1}!} ∑_{w∈S} e^{−d(w)/k} (\frac{d(w)}{k})^{i_{1}} | > δΔ) ≤ e^{−Cδ^{2}Δ}. (4)

In particular, when i_{1} = 0 and S = N(v), this says that, for every v ∈ V, c ∈ [k],

Pr (||{w ∼ v | c ∈ A(X_{t}, w)}| − ∑_{w∼v} e^{−d(w)/k}| > δΔ) ≤ e^{−Cδ^{2}Δ}. (5)

This will be applied in Section 6 to prove that our partial coupling is biased toward coalescence, assuming non-Markovian moves are available at all singly blocked steps.

Our next theorem establishes that, after sufficient burn-in, singly-blocked disagreements are typically swap-eligible, a central result of this paper. Although this is a statement about the time-evolution of the Glauber dynamics, and so cannot be simply described as establishing a certain property of the stationary distribution, it is nevertheless very similar in flavor to Theorem 15, which will be the main tool in its proof. Both theorems can be viewed as establishing that a uniformity property of the stationary chain is attained after O(n log n) steps from an arbitrary starting distribution.

Theorem 17. Let t ≥ C_{b}n log n, p ∈ V and c, c′ ∈ [k]. Then, with probability ≥ 1 − n^{−10}, at most δΔ neighbors of p are singly blocked for c, c′, but not swap-eligible at time t.

Proof. Let c be any color. Let w_{1}, …, w_{ℓ} be the neighbors of v for which color c is a swappable color at time t. For each w_{i}, let s_{i} denote the number of swappable colors for that vertex at time t. WLOG, assume s_{1} > s_{2} > ⋯ > s_{ℓ}. The main fact we need to establish is that this sequence is “more or less the same” for every color c. More precisely,

Claim 18. For every two colors c, c′,

Pr (|ℓ − ℓ′| > δΔ) ≤ e^{−Cδ^{2}Δ},

and moreover, for every i ≤ min ℓ, ℓ′,

Pr (|{i: |s_{i} − s′_{i}| > δk}| > δΔ) ≤ e^{−Cδ^{2}Δ}.

To see this, we first argue about a simpler notion of “swappable color,” in which we forget about the fact that dangerous vertices are disallowed, as well as color assigned to v at time t. Moreover, we also forget about the dependence on the t-epoch of w, instead making a time interval [t_{1}, t_{2}] a parameter of the notion.

Thus, c ∈ S′(w, t_{1}, t_{2}) if c ∈ A(X_{t_{1}}, w) and if no neighbor of w attempts color c at any time in [t_{1}, t_{2}].

Let δ^{∗} > 0 be chosen suitably. For every j ≥ 0, and v ∈ V, define

N^{j}(v) = {w ∈ N(v): d(w) ∈ (j, j + 1]δ^{∗}Δ}.

Thus N(v) is the disjoint union of N^{0}(v), N^{1}(v), …, N^{⌊1/δ^{∗}⌋}(v).

By (3), in the case S = N^{j}, i_{1} = 0, and summing over all i_{2}, we know that about exp(−jδ^{∗}Δ/k)|N^{j}| ± δΔ of the vertices in N^{j} have color c available at time t_{1}. An easy Chernoff argument shows that, of these, almost surely about an exp(−(t_{2}−t_{1})jδ^{∗}Δ/kn) fraction will have no neighbor attempt color c within the interval [t_{1}, t_{2}]. This establishes that, with high probability,

||\{w ∈ N^{j}: c ∈ S′(w, t_{1}, t_{2})\}| − |N^{j}| exp (− (1 + \frac{t_{2} − t_{1}}{n} ) \frac{jδ^{∗}Δ}{k})| < δΔ,

i. e., that the number of elements of N^{j} for which c is a swappable color, is largely independent of c.

Analogously combining the same Chernoff’s bound argument with (2) instead of (3), we find that, for all w ∈ N^{j}, with high probability,

||S′(w, t_{1}, t_{2})| − k exp (− (1 + \frac{t_{2} − t_{1}}{n} ) \frac{jδ^{∗}Δ}{k})| < δk.

Hence, for this simpler notion of swappable colors, the Claim holds.

From here, the key insight is that, at least over intervals of length O(n), we can treat what happens to the neighbors of v as if it had no impact on the evolution of X_{t} on the rest of G. More precisely, following [12], we define a directed graph G^{∗}, which is making all edges of G bi-directed, except those joining vertices at distance ≤ 3 from v, which are oriented to point toward v. As shown in that paper, over an interval of O(n) steps, there is a coupling of the Glauber dynamics on G^{∗} with that on G, for which, with high probability, the evolutions differ on at most ϵΔ neighbors of any vertex at distance ≤ 2 from v. Consequently, it is enough to consider the Glauber dynamics on G^{∗}.

Note that the distribution of successful recoloring times for neighbors w of v, even conditioned on the evolutions of their neighbors, depends only on the degree of w. Also, these recoloring times are fully independent (technically, this requires that we work with the continuous-time version of the dynamics; see [12] for more details). It follows that, when v is singly-blocked for colors c, c′, even conditioned on which neighbors w do the blocking, the distribution of the lengths of their t-epochs are basically unaffected. This implies that the full “t-epoch” version of Claim 18 follows from the [t_{1}, t_{2}] version which we have already shown.

By a similar argument, we see that, conditioned on the evolution outside N(v), the blocking neighbors of v are nearly uniformly chosen from those with the blocking color available. It follows by Claim 18 that, as long as the set of blocking neighbors is of size sufficiently small compared to 1/δ, the corresponding neighbors probably exist. This is almost certain by (4).

Finally, we argue that the corresponding colors probably exist. To see this, observe that, for every 0 < α < 1, the set of swappable colors for each vertex, is very likely to have about an α fraction from the set {1, …, ⌊αk⌋}. The same is true for its set of available colors. Now consider a complementary neighbor z′ for a blocking vertex z. Since the actual color X_{t}(z′) is essentially uniformly random in the available colors for z′, it follows that its index among the blocking vertex is also essentially random. Hence its corresponding color exists with probability close to 1 − δ.

Remark 19. The proof extends to the generalized Glauber dynamics essentially without modifications. This is discussed in some detail by Molloy in [18, Section 3].

6 Analysis of our Partial Coupling

In this section, we prove Lemma 7, which says that, assuming the initial colorings satisfy the burn-in properties of the previous section, our non-Markovian coupling decreases the expected value of our modified Hamming distance, ρ, defined in (1).

6.1 Well-behaved Dominating Chain

Our first step is to prove that the dominating chain, defined in Section 3.1, is usually “well-behaved” (see Section 3.2).

First, we prove a distributional upper bound on |D|.

Lemma 20. The distribution of |D| is stochastically dominated by the exponential distribution with mean exp(C_{pc}).

Proof. Our goal is to prove that, for every ℓ ≥ 1.

Pr (|D| ≥ ℓ) ≤ (1 − exp(−C_{pc}))^{ℓ} .  (6)

Let ℓ ≥ 1 be fixed.

For each i ≥ 1, let t_{i} be the time at which the i’th disagreement is generated (possibly counting the same vertex multiple times). Denote t_{0} = 0. Let η_{i} := t_{i} − t_{i−1} be the waiting time for the formation of the i’th disagreement. Conditioned on the evolution at all times in [0, t_{i}], the distribution of η_{i} is stochastically dominated by the exponential distribution with mean kn/iΔ, since at each step prior to t_{i} we have |D_{t}| ≤ i and thus the set D_{t} increases with probability at most iΔ/kn. Being somewhat generous, let us assume each η_{i} is an independent variable whose distribution is exponential with mean kn/iΔ. Our problem is now to bound the probability that η_{1} + ⋯ + η_{ℓ} < T_{pc}.

Now, consider the problem of collecting ℓ coupons, when each coupon is generated by a Poisson process with rate Δ/kn. The delay between collecting the i’th coupon and the i+1’st coupon is exponentially distributed with mean kn/(ℓ − i)Δ, and each delay is independent. Hence the time to collect all ℓ coupons has the same distribution as η_{1} + ⋯ + η_{ℓ}. But the event that the total delay is less than T_{pc} equals the intersection of the ℓ independent events that each coupon is generated at least once in [0, T_{pc}].

This in turn equals

(1 − (1 − \frac{Δ}{kn})^{T_{pc}})^{ℓ} .

Inequality (6) now follows from the inequality

1 − \frac{Δ}{kn} ≥ \frac{n}{n + 1} ≥ exp(−1/n),

which in turn follows from the fact that Δ ≤ min{k − 1, n}.

We will need the following easy fact, which can be viewed as an upper bound on any conditional expectation for an exponentially distributed random variable.

Observation 21. Let X be a random variable, exponentially distributed with mean μ, and let A be an event of probability p. Then

E (X 1(A)) ≤ p(μ + 1 − μ ln p).

Proof. Let us denote ℓ = ⌈ln(p)/ ln(1 − 1/μ)⌉ and q = Pr (X ≥ ℓ).

It is easily checked that the event A which maximizes E (X 1(A)) subject to the constraint Pr (A) = p, is the union of the event {X ≥ ℓ} and any sub-event of {X = ℓ − 1} whose probability is p − q.

In this case,

E (X 1(A)) = q(ℓ + μ) + (p − q)(ℓ − 1) = q(μ + 1) + p(ℓ − 1)
≤ p(μ + 1) − pμ ln p.

Our next lemma states that, when |D| is small, it is likely that D is well-behaved.

Lemma 22. For every ϵ, C_{pc} > 0 there exists C_{d} such that whenever G has maximum degree Δ ≥ C_{d} log n and girth g ≥ 11, k ≥ (1 + ϵ)Δ, T_{pc} = C_{pc}n, then

Pr (D is not well-behaved and |D| ≤ exp(2C_{pc})) ≤ \frac{2C_{pc} exp(6C_{pc})}{k}.

Proof. Recall that, by definition, there are two ways D may fail to be wellbehaved: repropagation of a disagreement, or nearly traversing a cycle. Repropagation: In round t, the probability of repropagation is bounded by |D_{t}|(|D_{t}| − 1) max_{w∈V} |Z(w)|/kn, since for repropagation, v_{t} must be in D_{t}, and c_{t} must be Z(w) for some w ∈ N(v_{t}) ∩ D_{t}. Since |Z(w)| ≤ |D| + 1, we conclude that the conditional probability of propagation in round t is less than |D|^{3}/kn, regardless of the history. Hence, by a union bound,

Pr (repropagation occurs and |D| ≤ exp(2C_{pc})) ≤ \frac{T_{pc} exp(6C_{pc})}{kn}
= \frac{C_{pc} exp(6C_{pc})}{k}. (7)

Nearly Completing a Cycle:

In order for D to be within four edges of containing a cycle, there must be some time t and vertices p, w ∈ ⋃_{t′<t} D_{t′}, such that

1. p and w are at distance 5 in G. Since G has girth ≥ 11, this implies there is a unique path from p to w.

2. v_{t} is the first vertex along the path from p to w, and is added to D_{t}.

3. p is the unique neighbor of v_{t} in D_{t−1}.

There are clearly fewer than |D|(|D| − 1) candidates for p and w. Since there are at most |D| colors which could cause v_{t} to be added to D_{t}, it follows by a union bound that

Pr (cycle nearly completed and |D| ≤ exp(2C_{pc})) ≤ \frac{C_{pc} exp(6C_{pc})}{k}, (8)

the same bound as in the repropagation case.

Summing (7) and (8) completes the proof.

6.2 Non-Markovian Updates

We next prove that it is unlikely that a non-Markovian update fails, i. e., that any singly blocked update occurs where the vertex is not swap eligible for the relevant colors.

Lemma 23. Assuming girth(G) ≥ 6 and k > (1 + ϵ)Δ, the probability that there exists T_{b} ≤ t ≤ T_{pc} such that v_{t} is singly blocked for c_{t}^{0} but not swap eligible is o(1).

Proof. We will prove the result under the assumptions that |D| < exp(2C_{pc}) and that D is well-behaved. We will also assume that the uniformity property of Theorem 17 holds at each step t ≥ T_{b}; namely, that for every vertex v and colors c, c′, at most δΔ neighbors are singly blocked for c, c′, but not swap eligible. From this, the general result will follow by Lemmas 20 and 22, together with Theorem 17.

In order for v_{t} to be singly blocked but not swap eligible, we must choose one of at most δΔ neighbors of one of at most exp(2C_{pc}) existing disagreements, and must choose a particular color. Hence, at each step, the probability of failing to be swap eligible is at most δΔ exp(2C_{pc})/kn < δ exp(2C_{pc})/n. So the total probability of failing to be swap eligible is at most

1 − (1 − δ exp(2C_{pc})/n)^{T_{pc}} ≤ 1 − exp(−δ exp(2C_{pc})C_{pc}) ≈ δ exp(2C_{pc})C_{pc}.

Since we are free to choose δ arbitrarily small compared to C_{pc}, the desired result follows.

6.3 Finishing off the Proof of Lemma 7

Now we are ready to prove Lemma 7, which bounds E (ρ(X_{T_{pc}}, Y_{T_{pc}})) unconditionally.

Proof of Lemma 7. For 0 ≤ t ≤ T_{pc}, we define a “good” event G(t) as follows:

1. For 0 ≤ t < T_{b}, G(t) is the event that for all 0 ≤ t′ ≤ t, all the properties of Section 5 are satisfied by X_{t}.

2. For T_{b} ≤ t ≤ T_{pc}, we further require that if v_{t} is singly-blocked for color c_{t}, then it is swap-eligible.

Note that by the results of Section 5, together with Lemma 23, the probability of G(T_{pc}) approaches 1. Combining this with Lemma 20 and Observation 21, we can effectively discount the contribution of the complement of G(T_{pc}) to the expectation of ρ(X_{T_{pc}}, Y_{T_{pc}}).

We will use the following notational shorthand. For 0 ≤ t ≤ T_{pc}, let ρ̃(t) be defined by

ρ̃(t) = ρ(X_{t}, Y_{t}) 1(G(t)) = \begin{cases}ρ(X_{t}, Y_{t}) & if G(t) \\ 0 & otherwise. \end{cases}

Note that ρ̃(0) = exp(d(v)/k), and ρ̃(T_{pc}) = E (ρ(X_{T_{pc}}, Y_{T_{pc}}) 1(G(T_{pc}))).

The broad outline of our proof is as follows. For the initial T_{m} steps of the coupling, where we are not considering any non-Markovian updates, we use the following easy bound (see, e.g., Jerrum’s paper [15]). For arbitrary X_{t}, Y_{t} ∈ Ω,

E (ρ̃(t + 1) | X_{t}, Y_{t}) ≤ (1 + (3Δ − k)e/nk)ρ̃(t) < (1 + 2e/n)ρ̃(t). (9)

For the final T_{m} steps of our coupling, it is possible that all the singlyblocking vertices involved in our non-Markovian updates remain disagreements at time T_{pc}. (However, we are still guaranteed that these disagreements will not spread.) By (4), the expected number of blocking vertices for any update is less than 10, conditioned on G(t − 1). This lets us make the following upper bound on the expected change in (modified) Hamming distance for the last T_{m} steps:

E (ρ̃(t + 1)) ≤ (1 + 20(3Δ − k)e/nk)ρ̃(t) < (1 + 40e/n)ρ̃(t). (10)

For the middle T_{pc} − 2T_{m} steps of our coupling, we will prove that, when C_{d} is chosen sufficiently large,

E (ρ̃(t + 1)) ≤ (1 − δ/n)E (ρ̃(t)),  (11)

for a suitable constant δ (of the same order of magnitude as ϵ). From (9),

(10) and (11) we then have

E (ρ̃(T_{pc})) ≤ (1 + 2e/n)^{T_{m}}(1 + 40e/n)^{T_{m}}(1 − δ/n)^{T_{pc}−2T_{m}} < 1/4, (12)

when C_{pc} is sufficiently large relative to δ and C_{m}.

Now let T_{m} < t < T_{pc}−T_{m} and condition on the good event G(t). In case a bad event occurs at time t+1, such as traversing a cycle, or a non-Markovian update failing, then ρ̃(t + 1) = 0, which would be the best possible outcome. Otherwise, observe that a ρ̃(t + 1) > ρ̃(t) exactly when the attempted update (v(t), c(t)) for X_{t} satisfies:

1. The color c(t) is the same as the color of the parent of v(t) in Y_{t}^{t};

2. The parent of v(t) is colored differently in the two chains; and

3. No neighbors of v(t), excluding its parent, have color c(t).

4. G(t + 1) holds.

By (5), when X_{t} and Y_{t} differ at a single vertex, the expected value of ρ̃(t + 1) − ρ̃(t) is, with high probability, about

\frac{1}{kn} ∑_{w∼v} exp(−d(w)/k) exp(d(w)/k) − \frac{A(X_{t}, v)}{kn} exp(d(v)/k) ≈ \frac{d(v) − k}{kn}
< −ϵ/2n.

(Making δ sufficiently small compared to ϵ allows us to treat the approximate equality above as an equality.) A similar argument shows that in general,

E (ρ̃(t + 1) | X_{t}, Y_{t}) < (1 − ϵ/2n)ρ̃(t).

Thus we have established the desired bound stated in inequality 11.

6.4 Proof of Main Theorem

We can now complete the proof of our main theorem.

Proof of Theorem 1. Given any two initial colorings Q_{0}, Q′_{0} ∈ Ω, we begin by “burning in” both colorings for T_{b} = Cn log n steps. Then, for 1 ≤ j ≤ 2 log n, we apply our T_{pc}-step non-Markovian coupling to the pair (Q_{T_{b}+(j−1)T_{pc}}, Q′_{T_{b}+(j−1)T_{pc}}) to define (Q_{T_{b}+jT_{pc}}, Q′_{T_{b}+jT_{pc}}). Because, when nonzero, ρ is always at least 1 and at most en, if we could show that

E (ρ(Q_{T_{b}+jT_{pc}}, Q′_{T_{b}+jT_{pc}}) | Q_{T_{b}+(j−1)T_{pc}}, Q′_{T_{b}+(j−1)T_{pc}})

≤ \frac{1}{2}ρ(Q_{T_{b}+(j−1)T_{pc}}, Q′_{T_{b}+(j−1)T_{pc}}), (13)

this would imply by induction that

E (ρ(Q_{T_{b}+2T_{pc} log n}, Q′_{T_{b}+2T_{pc} log n})) = O(1/n),

and hence by Markov’s inequality,

Pr (Q_{T_{b}+2T_{pc} log n} ≠ Q′_{T_{b}+2T_{pc} log n}) = O(1/n).

Although (13) is actually too strong to be true, the following weaker statement is true, and will suffice for our purposes.

X E (ρ(Q_{T_{b}+jT_{pc}}, Q′_{T_{b}+jT_{pc}}) | Q_{T_{b}+(j−1)T_{pc}}, Q′_{T_{b}+(j−1)T_{pc}})

≤ \frac{1}{2}ρ(Q_{T_{b}+(j−1)T_{pc}}, Q′_{T_{b}+(j−1)T_{pc}}), (14)

where X denotes the indicator variable for the event that all colorings on the path from Q_{T_{b}+(j−1)T_{pc}} to Q′_{T_{b}+(j−1)T_{pc}} satisfy the high probability statement in the hypothesis of Lemma 7. By a union bound, with probability ≥ 1 − n^{−8}, X is 1 for all j ≤ 2 log n and all of the interpolated colorings between Q_{T_{b}+(j−1)T_{pc}} and Q′_{T_{b}+(j−1)T_{pc}}. This will suffice for our desired conclusion.

For notational simplicity, we henceforth assume j = 1 for the rest of this proof. The general case follows with only trivial modifications.

In order to establish (14), we first need to extend the definition of our T_{pc}-step coupling to apply to arbitrary pairs of colorings, not just pairs which differ at a single vertex. To do this, we apply the path coupling technique of Bubley and Dyer [2].

Consider an arbitrary canonical ordering on V, say V = {v_{1} < v_{2} < ⋯ < v_{n}}, and let V_{i} = {v_{1}, …, v_{i}}. For T = T_{b} + jT_{pc}, for each 0 ≤ i ≤ n, we define W_{T}^{i} as the interpolation between Q_{T} and Q′_{T} with respect to V_{i} (see Definition 6). Compose the T_{pc}-step couplings guaranteed by Lemma 7 along this path. Applying the triangle inequality along the path W^{0}, …, W^{n}, we have

E (ρ(Q_{T +T_{pc}}, Q′_{T +T_{pc}}) | Q_{T_{b}}, Q′_{T_{b}}) ≤ ∑_{i=1}^{n} E (ρ (W_{T +T_{pc}}^{i−1}, W_{T +T_{pc}}^{i}) | W_{T_{b}}^{i−1}, W_{T_{b}}^{i}).

By Lemma 7, we have

XE (ρ(Q_{T +T_{pc}}, Q′_{T +T_{pc}}) | Q_{T} , Q′_{T} ) ≤ \frac{1}{2} ∑_{i=1}^{n} ρ (W_{T}^{i−1}, W_{T}^{i} ) ≤ \frac{1}{2}ρ(Q_{T} , Q′_{T}).

This completes the proof of (14), and hence of Theorem 1.

References

[1] D. J. Aldous. Random walks on finite groups and rapidly mixing Markov chains. In Séminaire de Probabilities XVII, 243–297. Springer-Verlag, 1983. Lecture Notes in Mathematics 986.

[2] R. Bubley and M. Dyer. Path coupling, Dobrushin uniqueness, and approximate counting. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 223–231, 1997.

[3] G. R. Brightwell and P. Winkler. Random colorings of a Cayley tree. In Contemporary combinatorics, 247–276, János Bolyai Math. Soc., Budapest, 2002

[4] A. Czumaj and M. Kutylowski, Delayed path coupling and generating random permutations. Random Structures & Algorithms, 17(3-4):238–259, 2000.

[5] W. Doeblin. Exposé de lat theorie des chaînes simples constantes de Markov à un nombre fini d’états. Rev. Math. Union Interbalkanique, 2:77– 105, 1938.

[6] D. Dubhashi and D. Ranjan. Balls and bins: a study in negative dependence. Random Structures and Algorithms, 13(2):99–124, 1998.

[7] M. Dyer and A. Frieze. Randomly colouring graphs with lower bounds on girth and maximum degree. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 579-587, 2001.

[8] M. Dyer, A. Frieze, T. Hayes, and E. Vigoda. Randomly colouring constant degree graphs. In Proceedings of the 45th Annual Symposium on Foundations of Computer Science, 582-589, 2004.

[9] M. Dyer and C. Greenhill On Markov chains for independent sets. J. Algorithms 35(1):17–49, 2000.

[10] M. Dyer, A. Sinclair, E. Vigoda, and D. Weitz. Mixing in Time and Space for Lattice Spin Systems: A Combinatorial View. Rand. Struct. Alg. 24(4): 461-479, 2004.

[11] A. Frieze and J. Vera. On randomly colouring locally sparse graphs, Preprint, 2004.

[12] T. P. Hayes. Randomly coloring graphs with girth at least five. In Proceedings of the 35th Annual ACM Symposium on Theory of Computer Science, 269-278, 2003.

[13] T. Hayes and A. Sinclair. A general lower bound for mixing of single site dynamics on graphs, Preprint, 2005.

[14] T. Hayes and E. Vigoda. Coupling with the stationary distribution and improved sampling for colorings and independent sets. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 971-979, 2005.

[15] M. R. Jerrum. A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Structures and Algorithms, 7(2):157–165, 1995.

[16] L. C. Lau and M. Molloy. Randomly colouring graphs with girth five and large maximum degree, Preprint, 2005.

[17] M. Luby and E. Vigoda Approximately counting up to four. In Proceedings of the 29th Annual ACM Symposium on Theory of Computer Science, 682-687, 1997.

[18] M. Molloy. The Glauber dynamics on colorings of a graph with high girth and maximum degree. In Proceedings of the 34th Annual ACM Symposium on Theory of Computer Science, 91-98, 2002.

[19] J. Salas and A. Sokal Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem. J. Statist. Phys. 86(3-4):551–579, 1997.

[20] E. Vigoda. Improved bounds for sampling colorings. J. Math. Phys. 41(3):1555-1569, 2000.