Randomly Coloring Graphs of Girth at Least Five

[Extended Abstract] ^{∗}

Thomas P. Hayes

University of Chicago 1100 East 58th Street Chicago, Illinois 60637

hayest@cs.uchicago.edu

ABSTRACT

We improve rapid mixing results for the simple Glauber dynamics designed to generate a random k-coloring of a bounded-degree graph.

Let G be a graph with maximum degree Δ = Ω(log n), and girth ≥ 5. We prove that if k > αΔ, where α ≈ 1.763 then Glauber dynamics has mixing time O(n log n). If girth(G)≥ 6 and k > βΔ, where β ≈ 1.489 then Glauber dynamics has mixing time O(n log n). This improves a recent result of Molloy, who proved the same conclusion under the stronger assumptions that Δ = Ω(log n) and girth Ω(log Δ). Our work suggests that rapid mixing results for high girth and degree graphs may extend to general graphs.

Analogous results hold for random graphs of average degree up to n^{1/4}, compared with polylog(n), which was the best previously known.

Some of our proofs rely on a new Chernoff-Hoeffding type bound, which only requires the random variables to be wellbehaved with high probability. This tail inequality may be of independent interest.

Categories and Subject Descriptors

G.2.2 [Discrete Mathematics]: Graph Theory—Graph algorithms; G.3 [Probability and Statistics]: [Markov processes, Probabilistic algorithms (including Monte Carlo)]; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems

General Terms

Algorithms, Theory.

Keywords

Glauber dynamics, graph coloring, Markov chain Monte Carlo,

∗A full version of this article is available on the author’s

website at www.cs.uchicago.edu/∼hayest/papers.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro�t or commercial advantage and that copies bear this notice and the full citation on the �rst page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior speci�c permission and/or a fee. STOC’03, June 9�11, 2003, San Diego, California, USA. Copyright 2003 ACM 1-58113-674-9/03/0006 ...$5.00.

posterior analysis, Chernoff bounds, concentration inequalities.

1. INTRODUCTION

The Glauber dynamics for randomly coloring graphs has attracted considerable attention in a variety of fields, including combinatorics [1], computer science [9], and statistical physics [13]. The dynamics is a simple Markov chain whose stationary distribution is uniformly distributed over proper k-colorings of a bounded degree graph. For algorithmic purposes we want to upper bound the rate of convergence to stationarity. This would give an efficient method to simulate the associated Gibbs distribution in physics [13], and an approximation algorithm for the corresponding #P-complete counting problem [9, 10].

We will specifically examine the “heat bath” version of Glauber dynamics, in which, starting from a given k-coloring of the graph G = (V, E), at each step, a vertex is selected at random, and its color changed to a random color not taken by a neighboring vertex. It is well-known that this Markov chain is ergodic when k > Δ + 1, where Δ is the maximum degree of the graph. By “mixing time,” we will mean the number of steps until the distribution is within total variation distance 1/2 of the stationary distribution. The chain is said to be “rapidly mixing” if the mixing time is polynomial in the size of G. It is clear that the mixing time must be Ω(n log n), since every vertex must be colored at least once. The outstanding conjecture in the area is that the mixing time is also O(n log n) for all k > Δ + 1. So far, we seem very far from the answer.

Jerrum [9] showed that, when k > 2Δ, the mixing time is O(n log n). His proof uses the coupling method, which has recently enjoyed many successful applications in theoretical computer science, e. g., [2, 5, 6, 8, 9, 11, 14].

Remarkably, Vigoda [14] showed that, when k > 11Δ/6, the mixing time is O(n^{2} log n), by comparing Glauber dynamics to a related, somewhat more complicated Markov chain. So far, no direct analysis of Glauber dynamics has been able to match this result for general graphs.

Whereas Jerrum [9] and Vigoda [14] analyze coupling in a worst case situation, Dyer and Frieze [5] avoid the worst case by running the chains for an initial “burn-in” period. The burn-in period is sufficiently long for all the vertices in the local neighborhood of a vertex to be recolored in a roughly independent way. This near-independence comes at the price of requiring G to have girth Ω(log log n). (The girth of a graph is the length of its shortest cycle.) This girth assumption forces dependencies to be “communicated” through long paths, effectively postponing them until after the time of interest. When the maximum degree is Ω(log n), and the girth is Ω(log Δ), Dyer and Frieze proved the mixing time is O(n log n) for k > 1.763Δ. The constant was subsequently improved to 1.489 by Molloy [11]. These results also apply with high probability to random graphs with edge density log n^{Θ(1)}/n.

Main Contributions

We extend the results of Dyer and Frieze and Molloy to a much broader class of graphs, by reducing the girth requirement to a constant. We will use the following notation.

Let α^{∗} = 1.763... denote the root of xe^{−1/x} = 1, and let β^{∗} = 1.489... denote the positive root of (1 − e^{−1/x})^{2} + xe^{−1/x} = 1. Let G be a graph on n vertices having maximum degree Δ and girth g.

Theorem 1. For every α > α^{∗}, there exists C such that if Δ ≥ C log n, g ≥ 5, and k ≥ αΔ, then the Glauber dynamics for k-coloring G has mixing time O(n log n).

Theorem 2. For every β > β^{∗}, there exists C such that if Δ ≥ C log n, g ≥ 6, and k ≥ βΔ, then the Glauber dynamics for k-coloring G has mixing time O(n log n).

These results may be considered evidence that the “Dyer and Frieze approach” can be extended to general graphs: previous work by Dyer, Greenhill, and Molloy [6] suggests that very short cycles are not an obstacle to rapid mixing; also, the degree requirement seems to be an artifact of our method of applying Chernoff’s bound, rather than an essential feature of the Markov chain.

The effect of our improved girth requirements is quite noticeable in the application to random graphs, which now handles graphs of average degree up to n^{1/4}, compared with the polylog(n) which was previously known.

Theorem 3. For every α > α^{∗} and β > β^{∗}, there exists C such that, if G is a random graph on n vertices whose edges are included independently with probability p, then with probability 1 − 1/poly(n),

1. if k ≥ αpn, and pn ∈ (C log n, C^{−1}n^{1/4}), then Glauber dynamics for k-coloring G has mixing time O(n log n).

2. if k ≥ βpn, and pn ∈ (C log n, C^{−1}n^{1/5}), then Glauber dynamics for k-coloring G has mixing time O(n log n).

The same conclusions hold when pn is an integer and G is uniformly selected from the set of regular graphs of degree pn.

Overview

Our approach is closely related to that of Dyer and Frieze [5] and Molloy [11], in that our primary goal is to prove that after an initial “burn in” period (allowing most vertices to be recolored at least once), the colorings generated by Glauber dynamics are, with high probability, “locally uniform” (made precise below). This local uniformity allows us to discount certain unfavorable configurations which might delay convergence of the chain.

The first such uniformity property, studied by Dyer and Frieze [5], is that the number of distinct colors in the neighborhood of a vertex v is not much more than if all colors were assigned independently, without regard for legality of the resulting coloring.

The second uniformity property, studied by Molloy [11], is that, for every vertex v and pair of colors c, c′, the number of neighbors of v having at least one neighbor with color c and one with c′ is about the same as if all colors were assigned independently, without regard for legality.

It is clear that the first local uniformity property fails to hold when V has large cliques. However, when G is triangle-free, after enough burn-in time, colorings generated by Glauber dynamics do have this property with high probability (see Section 4.1). We conjecture that the amount of burn-in time required is O(n), which would allow this property to be used for proofs of rapid mixing. Under the stronger assumption that G has girth ≥ 5, we are able to prove this conjecture (see Lemma 5).

Similarly, the second local uniformity property can fail– for instance, when G contains a complete bipartite subgraph K_{Δ,Δ}. But when G has girth ≥ 5, the uniformity property holds in the limit, and when G has girth ≥ 6, it holds after O(n) steps of Glauber dynamics (see Lemma 30).

Both Dyer and Frieze and Molloy proved their local uniformity properties using “paths of disagreement” arguments. The idea is to condition on the coloring at time t − Cn, and to use the assumption of large girth to establish that the colors assigned to neighbors of v at time t are very near to being fully independent. This is possible because any information about the first color assigned to a neighbor would have to be transmitted either through v, which is a bottleneck, or along a very long path, which is unlikely given only Cn steps. This method does not seem applicable in the constant girth setting.

At the heart of our approach is a posterior analysis of the Glauber dynamics, conditioned on the colors assigned at all but a few times of interest. By conditioning on more information, we gain more independence, at the price of having to work with slightly more complicated distributions.

The key property is that when the vertices selected at this time are at minimum distance 3, the conditional distribution is the product of its marginal distributions, allowing the application of Chernoff-type bounds. As a consequence, when girth(G) ≥ 5, if we pretend v does not affect the coloring, then, conditioned on the behavior of the rest of the graph, the colors assigned to the neighbors of v are independent. Moreover, it turns out that most of the neighbor colors are distributed almost uniformly over Ω(log n) possibilities. Chernoff-type bounds, together with a key lemma of Dyer and Frieze [5, Lemma 2.1], allow us to establish Theorem 1.

One notable feature of the present work, as well as those of Dyer and Frieze and Molloy, is that the main technical result, namely establishing local uniformity, has nothing to do with couplings; the coupling argument is essentially separate from the proof of local uniformity. However, because the earlier papers used a path coupling argument, the need arose to establish local uniformity for intermediate states which are not sampled from the same distribution, leading to some subtle technical issues. Our approach avoids these difficulties by eschewing path coupling in favor of the older method of general coupling.

Another feature of our work, which may be of independent interest, is Theorem 27, a generalization of the well-known tail inequalities of Chernoff, Hoeffding and Azuma (cf. [12, Chapter 4]), which allows the user to assume some “good” events occur when establishing the hypotheses. Of course, there is a penalty for this assumption, which is proportional to the probability that a “bad” event occurs.

In subsequent work with Eric Vigoda [8], we were able to improve Molloy’s constant, 1.489, to about 1.483, via analysis of a non-Markovian coupling. Those techniques seem to be orthogonal to the ones presented here.

Organization of the Paper

Sections 2–5 present a complete proof of Theorem 1. Section 2 first introduces essential terminology and notation used throughout the paper, then states the main technical lemmas required for Theorem 1. (Almost all are needed for Theorem 2 as well). Section 3 contains the proof of Theorem 1. Section 4 contains the proof of local uniformity via a posteriori analysis of Glauber dynamics. Section 5 contains proofs of the remaining technical results, including (Section 5.3) the general coupling argument.

Section 6 contains a fairly detailed outline of the proof of Theorem 2, including some of the proofs. Our improved version of Chernoff’s bound is proved in Section 6.1.

Section 7 contains a brief outline of Theorem 3. The next subsection can be skipped, but helps motivate

some of the technical notations introduced in Section 2.

The Big Picture

Here is a bird’s eye view of our approach to Theorem 1. We first require several properties of a random sequence of vertices, each of which is a relatively straightforward application of Chernoff-type inequalities.

Lemma 4. For every ϵ > 0, there exists C > 0 such that the following is true. Let G be a graph on n vertices having maximum degree Δ ≥ C log n and girth ≥ 5. Let t ≥ Cn be fixed. Choose σ : [T] → V (G) uniformly at random. Set v := σ(t). For every w ∈ Γ(v), let t_{w} = max{t′ < t | σ(t′) = w} be the last time before t that w was chosen (0 by default). Let T_{w} = {t_{w} < t′ < t | σ(t′) ∈ Γ(w)} be the times between t_{w} and t at which neighbors of w are chosen. Then, with high probability (≥ 1 − n^{−10}), there exists a set N of neighbors of v such that

1. |N| > |Γ(v)| − ϵΔ.

2. For every w ∈ N, |T_{w}| ≤ 2eCΔ.

3. σ(t) = v at fewer than ϵΔ times t ∈ ∪_{w∈N}T_{w}.

It turns out that the conclusions of Lemma 4 are enough to guarantee the local uniformity property of Dyer and Frieze:

Lemma 5. The conclusions of Lemma 4 imply that for a sequence f = (f_{0}, f_{1}, …, f_{T}), of k-colorings of G chosen according to Glauber dynamics, for every t > Cn,

Pr (A(f, t) < ke^{−Δ/k} − 3ϵΔ) < n^{−10},

where A(f, t) = k − #f_{t}(Γ(σ(t))) is the number of colors “available at time t.”

From this, Theorem 1 follows along the same lines as Jerrum’s original proof. Lemmas 4 and 5 will follow from the more general Lemmas 12 and 11 in the next section.

2. MAIN TECHNICAL LEMMAS

In this section, we present the model, our terminology, and the main technical lemmas required for the proof of Theorem 1, presented in Section 3.

We define the most pervasive notation first.

Notation 6. G = (V, E) will always denote a graph on n vertices with maximum degree Δ. We denote the neighbor set of a vertex v by Γ(v) := {w ∈ V (G) | {v, w} ∈ E}. When we speak of graph colorings, we shall always mean k-colorings, where k > Δ. We will also use the notation [N] := {1, …, N}, where N is a positive integer.

Before we formally define what we mean by “Glauber dynamics,” note that there is an alternative “Metropolis” version of Glauber dynamics on graph colorings, with which this should not be confused (although the mixing times of these two chains are known to differ by a factor of at most n in all cases). There are also versions of Glauber dynamics for sampling from other state spaces.

Definition 7. Glauber dynamics is a random process which generates a sequence f = (f_{0}, f_{1}, …, f_{T}), where each f_{i} : V (G) → [k] is a k-coloring of G. f_{0} may be distributed arbitrarily. Given f_{t−1}, f_{t} is determined by selecting a vertex v = σ(t) uniformly at random, and a color c uniformly at random from [k] \ f_{t−1}(Γ(v)). f_{t} is defined to equal f_{t−1} except at v, where f_{t}(v) = c. We call the vector f = (f_{0}, f_{1}, …, f_{T}) a coloring sequence drawn according to Glauber dynamics. We call the corresponding vertex sequence, σ : [T] → V (G), the coloring schedule. (Note that σ is just a uniformly random sequence of vertices).

It will sometimes be convenient to think of the coloring schedule σ as being determined before any of the colorings f_{1}, …, f_{T}. Since σ(t) is independent of f_{0}, …, f_{t−1}, this makes no difference.

As can be seen from the “paths of disagreement” argument used by Dyer and Frieze, the coloring schedule σ can be a substantial obstacle to the flow of color information through G. An important example occurs when G is bipartite and σ alternately recolors the two halves; in this case, the colors assigned to neighbor sets are completely independent, a fact which can be exploited to extend Dyer and Frieze’s result to bipartite graphs with maximum degree Ω(log n) (see [7]).

The following “influence sets,” I and F, will play an important role in our proof of Theorem 1. These are closely related to the “epochs” studied by Dyer and Frieze [5].

Definition 8. Fix a coloring sequence σ and a time t. We denote I(σ, t) := {i | i > t, σ(i) ∈ Γ(σ(t)), (∀t < t′ < i) σ(t′) ≠ σ(t)}. We will refer to I(σ, t) as the set of times directly influenced by t. Similarly, denote F(σ, t) := {i > 0 | t ∈ I(σ, i)}, the set of times with direct influence on t. When σ is understood, we omit it from the notation.

Note that for any fixed time t, the time sets I(σ, t) and F(σ, t) depend only the schedule σ, not the colors chosen at each time. Also note that, at time t, the set f_{t}(Γ(v)) of colors assigned to neighbors of v, is exactly the set of colors assigned at I(σ, t) (ignoring any neighbors of v which have never been recolored). It turns out that, in order to study this set of neighbor colors, it is often notationally more convenient to work with the time set I(σ, t) rather than the vertex set Γ(v). This motivates the following conventions.

Notation 9. Let σ be a coloring schedule. let T = T (σ) ⊆ [T] be a set of times. Let f be a coloring sequence with schedule σ. We denote f(T ) := {f_{t}(σ(t)) | t ∈ T } ⊆ [k] and σ(T ) := {σ(t) | t ∈ T (σ)} ⊆ V (G). We denote A(f, T ) := k − |f(T )|, the number of colors unused in f at times in T . For a single time t, we will sometimes write A(f, t) := A(f, F(t)), which is the number of unused colors in the neighbor set of σ(t) at time t.

We now define a notion of “goodness” for a time set T (σ), which we will later show implies a high probability of “local uniformity” (see Lemma 11).

Definition 10. For every coloring schedule σ : [T] → V (G), let T (σ) ⊆ [T] be a set of times. Let ϵ > 0. We say T is ϵ-good if, for σ chosen uniformly at random, with probability ≥ 1 − n^{−10}, there exists T′ ⊆ T (σ) such that (EG1) σ(T′) is an independent set of vertices, (EG2) |T′| ≥ |T (σ)| − ϵΔ, (EG3) for all t ∈ T′, |I(t)| < 2ecΔ, and (EG4) (∑_{t∈T ′} |I(t)|) − |⋃_{t∈T} I(t)| < log^{2} n.

Now we have all the definitions we need to state our main Lemmas. The first one, a generalization of Lemma 5, is our main tool for reducing the girth requirements, and is used in the proofs of Theorems 1 and 2.

Lemma 11. For every ϵ > 0, there exists C > 0 such that whenever G is a graph of maximum degree Δ ≥ C log n, and k ≥ (1 + ϵ)Δ, the following holds. Let T be ϵ-good. Let f_{0} : V → [k] be a given k-coloring. Select a random coloring sequence f = (f_{0}, …, f_{T}) according to Glauber dynamics. Then

Pr (A(f, T (σ(f))) < ke^{−|T |/k} − 2ϵΔ) < n^{−10}.

Section 4 is primarily devoted to the proof of Lemma 11. The next Lemma establishes that F(σ, t) is in fact ϵ-good

after an initial “burn-in” period of O(n) steps, assuming the graph has maximum degree Ω(log n) and girth ≥ 5. Combining this with Lemma 11 establishes the first local uniformity property, needed for Theorem 1.

Lemma 12. For every ϵ > 0, there exists C > 0 such that for every t > Cn and every graph G having girth ≥ 5 and maximum degree Δ ≥ C log n, the map F(·, t) is ϵ-good.

The proof is in Section 5.1.

The following result will be a key ingredient in the coupling argument used to prove Theorems 1 and 2. It also leads to a Chernoff-type bound, Theorem 27, which we will use, in Section 6 to establish Molloy’s local uniformity property.

Lemma 13. Let X_{0}, …, X_{N} be random variables taking values in [0, D], let B_{1} ⊆ ⋯ ⊆ B_{N} be a nested sequence of “bad” events, and let G_{i} = \overline{B_{i}} be the complementary “good” events. Suppose further that for 1 ≤ i ≤ N, E ( X_{i} | G_{i}) ≤ α_{i}E ( X_{i−1} | G_{i}), for some parameters α_{1}, …, α_{N}. Then

E (X_{N}) ≤ E (X_{0}) ∏_{ℓ=1}^{N} α_{ℓ} + D Pr (B_{N}) .

The proof is in Section 5.2.

The next result shows that local uniformity implies rapid coupling.

Theorem 14. Let G be a graph on n vertices with maximum degree Δ. Let f_{0}, …, f_{T} and g_{0}, …, g_{T} be maximally coupled copies of Glauber dynamics for k-colorings of G. Then

Pr (f_{T} = g_{T}) ≥ 1 − ne^{−T ϵ/n} − np,

where

p := Pr ((∃v∃t < T) (min\{A(f, t), A(g, t)\} < \frac{Δ}{1 − ϵ} )) .

The proof is in Section 5.3.

3. PROOF OF THEOREM 1

Let T = Cn log n. By the Coupling Theorem (cf. [9]), it is enough to show, for all initial colorings f_{0}, g_{0}, and two maximally coupled copies of Glauber dynamics, f = (f_{0}, …, f_{T}), g = (g_{0}, … g_{T}), that Pr (f_{T} = g_{T}) ≥ 1/2.

Let the number of colors be k = (α^{∗} + 2ϵ)Δ. Applying Lemma 11, assuming C is sufficiently large, and using the definition of α^{∗}, we find

Pr ((∃t > Cn) A(f, t) < \frac{Δ}{1 − ϵ} ) < n^{−10}.

By Theorem 14, applied to the last T − Cn steps of the chain,

Pr (f_{T} = g_{T}) ≥ 1 − 2/n − ne^{−(T −Cn)ϵ/n}.

For T > 2ϵ^{−1}n(ln n + C), this is at least 1 − 3/n, which is greater than 1/2.

4. ESTABLISHING LOCAL UNIFORMITY

The main goal of this section is to prove Lemma 11, which says that ϵ-good sets of times T (·, t) almost always miss about ke^{−|T (·,t)|} colors.

We begin by presenting a much simpler example which, in addition to motivating our technique, gives some hope that the method can be extended to work for all triangle-free graphs.

4.1 Random Colorings are Locally Uniform

Suppose we sample a proper k-coloring of G uniformly at random. How many distinct colors will not appear in the neighbor set of a vertex v?

We quickly look at three special cases. When G is the empty graph, we will almost certainly miss close to ke^{−Δ/k} colors, since each color is missed with probability (1−1/k)^{Δ} ≈ e^{−Δ/k}, and the assignments are independent.

When v is part of a Δ + 1-clique, we will miss exactly k − Δ distinct colors, since all the neighbor colors must be distinct.

When v is part of a K_{Δ,Δ}-subgraph, we expect with high probability to miss about x colors, where x(2 − e^{−Δ/x}) = k. (For this example, the proof is more difficult; see the full version for details)

Next we observe that for triangle-free graphs, as long as k > (1 + ϵ)Δ, the first local uniformity property holds with high probability for a uniformly random proper coloring.

This provides some intuitive justification for the general approach of trying to prove local uniformity properties for the Glauber dynamics: since we know these properties hold for the stationary distribution, they should also hold after the Glauber dynamics has run “long enough.”

Observation 15. Suppose G is triangle-free and has maximum degree Δ = Ω(log n). Let k > (1 + ϵ)Δ. Then for a random proper k-coloring f : V (G) → [k], with probability 1 − poly(1/n), for every vertex v, k − |f(Γ(v))| ≥ ke^{−Δ/k} − ϵΔ.

If we also exclude 4-cycles, a two-sided concentration result is possible:

Proposition 16. Suppose G is girth ≥ 5 and maximum degree Δ = Ω(log n). Let k > (1 + ϵ)Δ. Then for a random proper k-coloring f : V (G) → [k], with probability 1 − poly(1/n), for every vertex v, |k − |f(Γ(v))| − ke^{−Δ/k}| ≤ ϵΔ.

We remark that the example of a complete bipartite graph, discussed above, shows that the conclusion of Proposition 16 does not hold for all triangle-free graphs.

We will need the following result, due to Dyer and Frieze [5, Lemma 2.1]. It says that, in a sequence of independent color selections for which no one color is very likely in any stage, the number of missed colors will not be much less than if each color were chosen independently and uniformly from all of [k]. Although originally stated with the stronger hypothesis that each color is selected uniformly from a subset of [k], the original proof suffices for the current version as well. The weaker hypotheses stated here will be needed when we apply this result in Section 4.2.

Lemma 17 (Dyer and Frieze). Let k be a positive integer, and let D_{1}, …, D_{s} be probability distributions on the color set [k] such that under every D_{i}, no color has probability more than p. For 1 ≤ i ≤ s, let c_{i} be chosen according to D_{i}, independently of c_{1}, …, c_{i−1}. Let A := k −|{c_{1}, …, c_{s}}| be the number of unused colors. Then E (A) ≥ k (1 − p)^{s/kp} , and for every a > 0, Pr (A < E (A) − a) < e^{−a^{2}/2k}.

Proof of Observation 15. Let v be fixed. Select a proper k-coloring f uniformly at random. Select new colors for Γ(v) uniformly at random from among the available colors. The resulting coloring is distributed uniformly among k-colorings, since for any pair of proper colorings f, g, the probability of selecting f, then g, is the same as the probability of selecting g, then f.

But now we can see that the colors on Γ(v) are independent random variables, each drawn from a uniform distribution on at least k − Δ ≥ ϵΔ ≥ C log n colors! The result follows by Lemma 17.

4.2 Proof of Lemma 11

To prove our first local uniformity property, we need to answer the following question: if f = (f_{0}, …, f_{t}, …, f_{T}) is selected according to Glauber dynamics, how can we prove a tail law for A(f, t)?

Straightforward approaches are hampered by (potentially) complex dependencies among the random variables f_{t}(u), u ∈ Γ(σ(t)).

Our approach is to gather more information before answering the question. Suppose that, for some vertex set U, we are told everything about f except the |U| values f_{t}(u), u ∈ U. Conditioned on this extra information, the distribution of f may be much simpler, since there are many fewer possibilities to consider. In fact, if U has minimum distance 3, then the random variables f_{t}(u) turn out to be fully independent, allowing us to prove strong tail inequalities for the posterior distribution of f_{t}(U).

First, we will need some more notation and terminology.

Definition 18. Fix a coloring schedule σ : [T] → V. Let f, g be two coloring sequences with schedule σ, such that f_{0} = g_{0}. Let T ⊆ [T] be a set of times. If

(∀t ∉ T ) f_{t}(σ(t)) = g_{t}(σ(t)),

then we say that f and g agree except at times in T . Note that this is an equivalence relation on the space of coloring sequences.

We are interested in the following experiment. For every coloring schedule σ suppose T = T (σ) ⊆ [T] is a set of times such that the vertex set σ(T ) is guaranteed to have all pairwise distances at least 3. Let f be a coloring sequence with schedule σ. Select a coloring sequence g according to the posterior distribution of Glauber dynamics conditioned on the event that g has schedule σ and agrees with f except at times in T . Then (Lemma 20) for any fixed f, the random variables g_{t}(σ(t)), t ∈ T , are fully independent, and moreover, for most σ, for most f, for most t ∈ T (σ), the distribution of g_{t}(σ(t)) is “roughly uniform” on a set of Ω(log n) colors. This allows us to prove strong tail estimates on A(g, T ). This approach generalizes to the case when T is only ϵ-good, rather than distance 3, although the variables g_{t}(σ(t)), t ∈ T are no longer independent. Finally, Lemma 11 follows because f has the same distribution as g, as seen from the following observation.

Observation 19. Let ∼ be an equivalence relation on a finite set S. Let D be a probability distribution on S. Sample X, Y ∈ S as follows: draw X according to D, then draw Y according to D conditioned on Y ∼ X. Then Y is distributed according to D.

Proof. Let \overline{z} ∈ S/ ∼ be any equivalence class induced by ∼. Then, for every x, y ∈ \overline{z},

Pr ( (X, Y) = (x, y) | X ∈ \overline{z})
= Pr ( X = x | X ∈ \overline{z}) Pr ( Y = y | Y ∈ \overline{z}) .

Since Y ∈ \overline{z} iff X ∈ \overline{z}, the right-hand side is symmetric in X and Y, therefore X and Y can be switched on the lefthand side too, which implies the result. Moreover, we see that the distribution of (X, Y) within \overline{z} × \overline{z} is a product distribution.

Our next lemma says that if the vertex set σ(T ) has minimum distance ≥ 3, then the distribution of g is the product of its marginal distributions. Also, the nonuniformity of these marginal distributions is bounded in terms of the influence sets I(σ, t), t ∈ T .

Lemma 20. Fix a coloring schedule σ : [T] → V and a proper coloring sequence f. Let T ⊆ [T] be a set of times such that σ(T ) is an independent set, and such that the sets I(t), t ∈ T are pairwise disjoint. Select a coloring sequence g according to Glauber dynamics, conditioned on the event that g agrees with f except at times in T . Then the random variables g_{t}(σ(t)), t ∈ T , are fully independent. Moreover, for every t ∈ T , c, c′ ∈ [k] such that Pr (g_{t}(σ(t)) = c) ≠ 0,

Pr (g_{t}(σ(t)) = c′) ≤ (1 + \frac{1}{k − Δ} )^{|I(t)|} Pr (g_{t}(σ(t)) = c) .

Proof. Let h be a coloring sequence which agrees with f. A priori, given only that g is selected according to Glauber dynamics with coloring schedule σ,

Pr (g = h) = ∏_{i=1}^{T} \frac{1}{A(h, i)} .

By our assumption that the sets I(t), t ∈ T are pairwise disjoint, we can write

Pr (g = h) = C ∏_{t∈T} ∏_{i∈I(t)} \frac{1}{A(h, i)} ,  (1)

where C := ∏ ; i∉⋃_{t} I(t) \frac{1}{A(h, i)} does not depend on any h_{t}(σ(t)),

t ∈ T , and hence is constant for all h which agree with f except at times in T .

Now let us take into account the additional information that g agrees with f except at times in T . Bayes’ Law says that posterior probabilities are in the same proportion as the original probabilities, except for those values which are ruled out by the new information. Thus the product decomposition in (1) implies the independence of the variables g_{t}(σ(t)), t ∈ T .

Moreover, the ratios of the a posteriori probabilities are bounded by the maximum ratio of the terms in (1), which is easily seen to be ≤ max_{t∈T} (1 + 1/(k − Δ))^{|I(t)|}. We leave the details to the full version.

Next we use Lemma 20, together with Chernoff’s bound, to derive, for each σ, T , f, a tail law on A(g, T ), assuming only that σ(T ) is an independent set. There are trade-offs between the strength of the tail law and the size and overlap of the influence sets I(t), t ∈ T , as well as the number of distinct colors possible for each g_{t}(σ(t)).

Lemma 21. Fix a coloring schedule σ : [T] → V and a proper coloring sequence f. Let T ⊆ [T] be a set of times such that σ(T ) is an independent set. Select a coloring sequence g according to Glauber dynamics, conditioned on the event that g agrees with f except at times in T . Then, for every a > 0,

Pr(A(g, T )< k(1 − p)^{|T |/kp} − a) < (1 + \frac{1}{k − Δ} )^{R}e^{−a^{2}/2|T |},

where, for each t ∈ T ,

d_{t} := |{c | Pr (g_{t}(σ(t)) = c) ≠ 0}|
p := max_{t∈T} \frac{1}{d_{t}} (1 + \frac{1}{k − Δ} )^{|I(t)|} , and

R := (∑_{t∈T} |I(t)|) − | ⋃_{t∈T} I(t)| .

Remark 22. Note that if σ(T ) has minimum distance ≥ 3, then R = 0. As another example, if σ(T ) = Γ(v) and G has girth ≥ 5, then R is a weighted count of how often v is recolored at times “influenced by T .”

Proof. First, let us suppose R = 0, i. e., that the sets I(t), t ∈ T , are pairwise disjoint. Then by Lemma 20, we know the random variables g_{t}(σ(t)), t ∈ T , are fully independent, and that the probabilities of the d_{t} possible values are all within a factor (1 + 1/(k − Δ))^{|I(t)|} of each other; hence each of these probabilities is at most p. Thus we are in exactly the setting of Lemma 17, which gives the desired conclusion.

In the case R > 0, the g_{t}(σ(t)) are no longer independent, so we first approximate them by a set of random variables which are. As in the proof of Lemma 20, we express the a priori distribution of g, selected according to Glauber dynamics, as

Pr (g = h) = ∏_{i=1}^{T} \frac{1}{A(h, i)} = C ∏ ; i∈⋃_{t∈T} I(t) \frac{1}{A(h, i)} ,

where C := ∏_{i∉⋃_{t∈T} I(t)} \frac{1}{A(h,i)} does not depend on any of the values assigned at times in T .

Let g′ be a coloring sequence which agrees with f except at times in T , and drawn with probabilities proportional to

∏_{t∈T} ∏_{i∈I(t)} \frac{1}{A(h, i)} .

Relative probabilities of events are somewhat distorted in this new distribution: for coloring sequences h,h′ we have

Pr (g′ = h′) ; Pr (g′ = h) ≤ Pr (g = h′) ; Pr (g = h) (1 + \frac{1}{k − Δ} )^{R} ,

since, for every i, A(h, i) is determined to within 1, and min A(h, i) ≥ k − Δ.

From Lemma 17 applied to g′, we know that

Pr (A(g′, T ) < k(1 − p)^{|T |/kp} − a) < e^{−a^{2}/2|T |},

But g′ can be thought of as g, except with atoms distorted

by up to F = (1 + \frac{1}{k−Δ} )^{R}, hence the probability of any event in the original space is not more than F times the probability in the new space. Thus

Pr (A(g′, T ) < k(1 − p)^{|T |/kp} − a) < F e^{−a^{2}/2|T |},

which was to be proved.

We are at last ready to prove Lemma 11.

Proof of Lemma 11. Choose a coloring schedule σ uniformly at random. Since T is ϵ-good, with probability at least 1 − n^{−10}, there exists an independent subset T′ ⊆ T

such that |T′| ≥ |T | − ϵΔ, ( ∑_{t∈T ′} |I(t)|) − | ⋃_{t∈T ′} I(t)| <

log^{2} n, and for all t ∈ T′, |I(t)| < 2ecΔ,

Randomly choose f according to Glauber dynamics with coloring schedule σ. Now choose g according to Glauber dynamics for G, conditional on g agreeing with f except at times in T . Recall that, by Observation 19, g has the same distribution as f. Thus, it will suffice to prove the tail inequality for A(g, T )

Applying Lemma 21 to T′ with a = ϵΔ,

Pr (A(g, T′) < k(1 − p)^{|T ′|/kp} − ϵΔ)
< (1 + \frac{1}{k − Δ} )^{R} e^{−ϵ^{2}Δ^{2}/2|T ′|}  (2)

where, for each t ∈ T′, d_{t} := |{c | Pr (g_{t}(σ(t)) = c) ≠ 0}|,

p := max_{t∈T ′} \frac{1}{d_{t}} (1 + \frac{1}{k−Δ} )^{|I(t)|}, and R := (∑_{t∈T ′} |I(t)|)−

|⋃_{t∈T ′} I(t)| < log^{2} n.

Fixing t ∈ T′, the probability that a particular color does

not occur in I(t) is ≥ (1 − \frac{1}{k−Δ} )^{2ecΔ}, which is greater

than exp(−2ecΔ/(k − Δ − 1)) =: e^{−C′}. Now, since the events “color c is missed” are negatively dependent (see Dubhashi and Ranjan [4, Theorem 46]), we can apply Proposition 24, proving that with probability ≥ 1−n^{−10} (for suitably large Δ), not fewer than ke^{−C′−1} colors are missed. Hence p = O(1/ log n). Using the inequality (1 − p)^{|T ′|/kp} ≥ e^{−|T ′|/k}(1 − p)^{|T ′|/k} (cf. [12, p. 435, Prop B.3.2]), together with the observations above, inequality (2) can be used to derive

Pr (A(g, T′) < ke^{−|T ′|/k} − ϵΔ) < n^{−10}

as long as Δ ≥ C log n, where C is suitably (exponentially) large relative to 1/ϵ. Since T has at most ϵΔ elements more than T′, this establishes the desired inequality.

5. TECHNICAL LEMMAS

5.1 Proof of Lemma 12

In order to prove Lemma 12, we shall need to establish several large-deviation bounds. To do this, it will be convenient to use a generalized version of the usual Chernoff-Hoeffding bounds (due to Dubhashi and Ranjan [3, 4]) which holds for random variables which are “negatively associated”, rather than independent.

Definition 23. Suppose X_{1}, …, X_{n} are random variables such that for any two disjoint subsets I, J ⊂ [n], and any two increasing functions f : ℝ^{|I|} → ℝ, g : ℝ^{|J|} → ℝ,

E (f ((X_{i})_{i∈I}) g ((X_{j})_{j∈J})) ≤ E (f ((X_{i})_{i∈I})) E (g ((X_{j})_{j∈J})) .

Then we say X_{1}, …, X_{n} are negatively associated.

A very useful property is that non-decreasing functions of disjoint subsets of a set of negatively associated random variables are also negatively associated [4, Proposition 1.7]. The following result is Proposition 1.5 in [4]

Proposition 24 (Dubhashi–Ranjan [4]). Suppose X_{1}, …, X_{n} are negatively associated [0, 1]-valued random variables. Let X = ∑_{i=1}^{n} X_{i}. Then for every δ > 0,

Pr (X ≤ (1 − δ)E (X)) < e^{−δ^{2}E(X)/2}, and
Pr (X ≥ (1 + δ)E (X)) > ( \frac{e^{δ}}{(1 + δ)^{1+δ}} )^{E(X)} .

We now present a detailed sketch proof of Lemma 12.

Proof of Lemma 12. Since by definition,

σ(F(σ, t)) = {w ∈ Γ(v) | w ∈ σ([t])} ⊆ Γ(v),

the independence condition (EG1) of Definition 10 automatically holds.

For each w ∈ V (G), let X_{w} be the number of times w was recolored during the last Cn time steps prior to t, i. e., X_{w} := |{t′ ∈ [t − Cn, t − 1] | σ(t′) = w}|. Similarly, let Y_{w} := |{t′ ∈ [t, t + Cn] | σ(′t) = w}|. To establish that F(·, t) is ϵ-good, it will suffice to establish the following assertions:

(A1) Pr (|\{w ∈ Γ(v) | X_{w} = 0 or Y_{w} = 0\}| ≥ ϵΔ) < \frac{1}{4} n^{−10}.

(A2) Pr (X_{v} + Y_{v} ≥ ϵΔ) < \frac{1}{4} n^{−10}.

(A3) Pr ((∃w ∈ Γ(v)) (∑_{x∈Γ(w)} X_{x} + Y_{x} > 2ecΔ)) < \frac{1}{2} n^{−10}.

To see this, note that with probability at least 1 − n^{−10}, none of these three events occurs. Setting

T′ := {t′ ∈ F(σ, t) | I(σ, t′) ⊆ [t − Cn, t + Cn]}
= {t′ ∈ F(σ, t) | X_{σ(t′)} ≠ 0 and Y_{σ(t′)} ≠ 0},

assertion (A1) implies |T′| ≥ |F(σ, t)| − ϵΔ, which is condition (EG2) of Definition 10. Note that T′ was defined so that, for every t′ ∈ T′, we have I(t′) ⊆ [t − Cn, t + Cn]. Hence assertion (A3) implies condition (EG3) of Definition 10. Finally, condition (EG4) of Definition 10 follows from assertion (A2), since v is the only common neighbor of σ(T′). All that remains is to prove assertions (A1)–(A3). We only sketch this part of the proof.

Assertion (A1) relies on the fact that the events {X_{w} = 0} and {Y_{w} = 0} are negatively associated, and that consequently Proposition 24 applies (see also [4, Theorem 46]).

Assertion (A2) is just Chernoff’s bound, relying on the independence of the selected vertices σ(t−Cn), …, σ(t−1).

Now we prove assertion (A3). First, in light of assertion (A1), we may discount the effect of v on ∑_{x∈Γ(w)} X_{x} + Y_{x}. Then, the probability that ∑_{x∈Γ(w)\{v}} X_{x} + Y_{x} exceeds (2ec − ϵ)Δ is at most e^{−c} by Chernoff’s bound. Call this event Z_{w}. Since girth(G) ≥ 5, the sets Γ(w) \ {v} are disjoint. Thus the events Z_{w} are increasing functions of disjoint sets of negatively associated random variables, and so they are negatively associated^{1} (see [4, Proposition 7]). Hence Proposition 24 applies, which gives the desired result.

Remark: the dependence of C on 1/ϵ is exponential.

5.2 Proof of Lemma 13

Proof. We prove the stronger claim that, for every 0 ≤ i < N, 0 ≤ j ≤ N − i,

E ( X_{i+j} | G_{i}) ≤ E ( X_{i} | G_{i}) ∏_{ℓ=i+1}^{i+j} α_{ℓ} + D Pr ( B_{i+j} | G_{i}) .

Specializing to the case i = 0, j = N gives the desired result. The proof is by induction on j. The base case j = 0 holds with equality, since B_{i} and G_{i} are complements.

Let 0 ≤ i < N, 1 ≤ j ≤ N − i. Since G_{i+1} ⊆ G_{i}, we can rewrite E ( X_{i+j} | G_{i}) = E ( X_{i+j} | G_{i+1}) Pr ( G_{i+1} | G_{i}) +E ( X_{i+j} | B_{i+1}, G_{i}) Pr ( B_{i+1} | G_{i}). Applying the inductive hypothesis to bound E ( X_{i+j} | G_{i+1}) yields

E(X_{i+j} | G_{i}) ≤ (E(X_{i+1} | G_{i+1}) ∏_{ℓ=i+2}^{i+j} α_{ℓ} + D Pr ( B_{i+j} | G_{i+1}))
×Pr ( G_{i+1} | G_{i}) + D Pr ( B_{i+1} | G_{i}) .

Applying the initial hypothesis that E ( X_{i+1} | G_{i+1}) ≤

1Note that this negative association would fail to hold if the case x = v were left in the sums. α_{i+1}E ( X_{i} | G_{i+1}), we obtain

E(X_{i+j} | G_{i}) ≤ (E(X_{i} | G_{i+1}) ∏_{ℓ=i+1}^{i+j} α_{ℓ} + D Pr ( B_{i+j} | G_{i+1}))

×Pr ( G_{i+1} | G_{i}) + D Pr ( B_{i+1} | G_{i}) .

Finally, rearranging terms and applying the law of total probability (twice), the previous expression simplifies to

E ( X_{i} | G_{i}) ∏_{ℓ=i+1}^{i+j} α_{ℓ} + D Pr ( B_{i+j} | G_{i})

−E ( X_{i} | B_{i+1}, G_{i}) Pr ( B_{i+1} | G_{i}) ∏_{ℓ=i+1}^{i+j} α_{ℓ}.

Dropping the last term leaves the desired upper bound.

5.3 Proof of Theorem 14

Proof. For 1 ≤ j ≤ T, define the “bad” event

B_{j} := \{(∃v ∃t < j) (min\{A(f, t), A(g, t)\} < \frac{Δ}{1 − ϵ} )\} .

Let G_{1}, …, G_{T} denote the corresponding complementary “good” events. By definition, p = Pr (B_{T}). Let H_{t} := H(f_{t}, g_{t}) denote the Hamming distance at time t.

Let 1 ≤ t ≤ T. We compute an upper bound on the expected change in Hamming distance, assuming no bad events. Fix particular values for f_{0}, g_{0}, f_{1}, g_{1}, …, f_{t−1}, g_{t−1} from the good event G_{t}. Assuming these values, we have

E (H_{t}) = ∑_{v∈V (G)} Pr (v not selected and f_{t−1} ≠ g_{t−1})

+ ∑_{v∈V (G)} Pr (v selected and f_{t} ≠ g_{t})

≤ \frac{n − 1}{n} H_{t−1} + \frac{1}{n} ∑_{v∈V (G)} \frac{# bad neighbors of v}{min\{A(f, t), A(g, t)\}} ,

where a neighbor w ∈ Γ(v) is called “bad” if f_{t−1}(w) ≠ g_{t−1}(w). Since the event G_{t} occurred, we are guaranteed that the denominators of terms in the sum are all at least Δ/(1 − ϵ), hence

E (H_{t}) ≤ \frac{n − 1}{n} H_{t−1} + \frac{1 − ϵ}{n Δ} ∑_{v∈V (G)}# bad neighbors of v

= (1 − \frac{ϵ}{n} )H_{t−1},

where the last step follows because the set of “vertex, bad neighbor” pairs equals the set of “bad vertex, any neighbor” pairs, and so has cardinality H_{t−1}Δ.

Averaging over the event G_{t}, we find that E ( H_{t} | G_{t}) ≤ (1 − \frac{ϵ}{n} )E ( H_{t−1} | G_{t}). Setting X_{i} := H_{i} for 0 ≤ i ≤ T, we are in exactly the setting of Lemma 13, which implies the desired result, considering that n is an absolute upper bound on the Hamming distance.

6. REACHING THE 1.498 THRESHOLD

Although we lack space for a complete proof of the Theorem 2, we shall nevertheless be able to give a fairly detailed outline. We begin by presenting a (to our knowledge) new concentration inequality, which will be one of our main tools.

6.1 A Chernoff-type bound

We first state a general tail inequality of Chernoff type.

Lemma 25. Let X_{1}, …, X_{N} be random variables taking values in [0, 1], and let B_{1} ⊆ ⋯ ⊆ B_{N} be a nested sequence of “bad” events, with complementary “good” events G_{i} = \overline{B_{i}}. For 1 ≤ i ≤ N, suppose that E ( X_{i} | X_{1}, X_{2}, …, X_{i−1}, G_{i}) ≤ p_{i}. Let μ := ∑_{i=1}^{N} p_{i}. Then for every δ > 0,

Pr (∑_{i=1}^{N} X_{i} > (1 + δ)μ)

< min_{λ>0} e^{−λμ(1+δ)} (e^{λN}Pr (B_{N}) + ∏_{i=1}^{N}(1 + p_{i}(e^{λ} − 1)))

Proof. Let λ > 0 be arbitrary. For 0 ≤ i ≤ N, define Y_{i} = exp (λ ∑_{j=1}^{i} X_{i}). Following the usual approach, we observe that Pr (X > (1 + δ)μ) = Pr (Y_{N} > exp((1 + δ)λμ)) = Pr (exp(−(1 + δ)λμ)Y_{N} > 1) < exp(−(1 + δ)λμ)E (Y_{N}), by Markov’s inequality. Our goal is now to get a good upper bound on E (Y_{N}).

For every 1 ≤ i ≤ N,

E ( Y_{i} | G_{i}) = E ( E ( Y_{i} | X_{1}, X_{2}, …, X_{i−1}, G_{i}) | G_{i}) .

Since Y_{i} = e^{λX_{i}}Y_{i−1}, and Y_{i−1} is a function of X_{1}, …, X_{i−1}, this becomes

E ( Y_{i} | G_{i}) = E ( Y_{i−1}E ( e^{λX_{i}} | X_{1}, X_{2}, …, X_{i−1}, G_{i}) | G_{i}) .

Since exp(λt) is a convex function, it follows that, among all random variables V with expectation p and taking values in [0, 1], the ones which maximizes E (exp λV) are {0, 1}- valued. Thus

E ( exp(λX_{i}) | …) ≤ max_{p≤p_{i}}(1 + p(e^{λ} − 1)) = 1 + p_{i}(e^{λ} − 1).

Thus, by averaging, we see that

E ( Y_{i} | G_{i}) ≤ (1 + p_{i}(e^{λ} − 1))E ( Y_{i−1} | G_{i})

for all 1 ≤ i ≤ N. The result follows by applying Lemma 13 to Y_{0}, …, Y_{N}.

Remark 26. A very similar version applies when lower bounds are known for E ( X_{i} | X_{1}, …, X_{i−1}, G_{i}). We leave the nearly identical statement and proof for the full version.

Many variants of Lemma 25 can easily be constructed by making simplifying assumptions of different kinds. The following is a natural choice which achieves the usual Chernoff’s bound when the probability of bad events is zero. It is far from optimal when the bad event probability is larger.

Theorem 27. Let X_{1}, …, X_{N} be random variables taking values in [0, 1], and let B_{1} ⊆ ⋯ ⊆ B_{N} be a nested sequence of “bad” events, with complementary “good” events G_{i} = \overline{B_{i}}. For 1 ≤ i ≤ N, suppose that

E ( X_{i} | X_{1}, X_{2}, …, X_{i−1}, G_{i}) ∈ [m_{i}, M_{i}].

Let m := ∑_{i=1}^{N} m_{i} and M := ∑_{i=1}^{N} M_{i}. Then for all δ > 0,

Pr(∑_{i=1}^{N} X_{i} > (1 + δ)M)< ( \frac{e^{δ}}{(1 + δ)^{1+δ}} )_{M}

+Pr (B_{N}) (1 + δ)^{N−(1+δ)M}

and Pr (∑_{i=1}^{N} X_{i} < (1 − δ)m) < e^{−δ^{2}m/2} + Pr (B_{N}) e^{m(δ−δ^{2}/2)}.

Proof. For the first inequality, substitute λ = ln(1 + δ) in Lemma 25. The second inequality follows from the unstated lemma mentioned in Remark 26, after substituting λ = − ln(1 − δ).

We remark that Theorem 27 can also be viewed as a generalization of the unweighted version of the Azuma-Hoeffding inequality. See the full version for details.

6.2 Sketch of Theorem 2

For several reasons, Theorem 2 is more technically difficult to prove that Theorem 1. Most of these difficulties were already present in Molloy’s original setting [11], and are resolved here more or less the same way.

We will make the simplifying assumption that G is Δregular. This is a justifiable assumption because low-degree vertices actually cause Glauber dynamics to couple faster, as can be seen from Jerrum’s original proof [9] (a disagreement at a low-degree vertex has few neighbors to which it can spread). However, low-degree vertices do not benefit from the second local uniformity property, and therefore have to be handled by a more or less separate argument. In the full version, we follow Molloy’s approach of using a weighted Hamming metric in our coupling argument.

First we need to establish an upper bound on the number of colors available at each vertex. Combined with Lemma 5, this establishes a two-sided concentration inequality.

Lemma 28. For every ϵ > 0, there exists C > 0 such that for every t > Cn and Δ-regular graph G having girth ≥ 6 and degree Δ ≥ C log n, when f = (f_{0}, …, f_{T}) is selected according to Glauber dynamics,

Pr (A(f, t) > ke^{−Δ/k} + ϵΔ) < n^{−10}.

The proof will rely on the following technical lemma, which we state without proof.

Definition 29. For all t ∈ [T] and i ∈ [|F(σ, t)|], let G_{t,i}(σ) := {t_{1}, …, t_{i−1}} ∪ F(σ, t_{i}), where F(σ, t) = {t_{1} < t_{2} < ⋯ < t_{|F(σ,t)|}}.

Lemma 30. For every ϵ > 0, there exists C > 0 such that for every t > Cn, 1 ≤ i ≤ d(v), and graph G having girth ≥ 6 and maximum degree Δ ≥ C log n, the map G_{t,i} is ϵ-good.

The proof of Lemma 30 proceeds along very similar lines to that of Lemma 12, so we omit it from this abstract.

The proof of Lemma 28 follows Molloy’s approach of splitting the burn-in period into a sequence of stages; during each stage we establish an improved bound, building inductively on the bound from the previous stage.

Proof. (Sketch proof of Lemma 28). Let ϵ′ > 0 be suitably small (how small will be seen later). Throughout the proof, “high probability” will mean probability 1 − n^{−c}, where c is some positive integer, such as 10. We will break the burn-in interval, [Cn], into many smaller intervals, [C′n], [C′n + 1, …, 2C′n], . . .. During each interval [jC′n+1, (j +1)C′n], we will establish by induction that for every t ≥ jC′n+1, A(f, t) < (1+η_{j})ke^{−Δ/k} with high probability, where η_{0}, η_{1}, η_{2}, …, is a decreasing sequence with η_{0} = e^{Δ/k} − 1 and η_{C/C′} = ϵ. The base case j = 0 is trivial by definition of η_{0}.

Let j ≥ 1, and suppose t ≥ jC′n + 1. Let v = σ(t). Chernoff’s bound can be used to show that, with high probability, |F(σ, t) ∩ [(j − 1)C′n + 1, t]| ≥ (1 − ϵ′)Δ. For simplicity, we will assume that F(σ, t) ⊂ [(j − 1)C′n + 1, t]. Let F(σ, t) = {t_{1} < t_{2} < ⋯ < t_{Δ}}, and for 1 ≤ i ≤ Δ, let w_{i} := σ(t_{i}), so that Γ(v) = {w_{1}, …, w_{Δ}}.

Now, exposing the colors in f(F(σ, t)) one by one, the total number of colors equals the number of steps at which a “new” color is seen. For 1 ≤ i ≤ Δ, let X_{i} be the 0 − 1 indicator variable for the event that a “new” color is seen at time t_{i}. Then k − A(f, t) = ∑_{i=1}^{Δ} X_{i}. On the other hand,

E ( X_{i} | f_{0}, f_{1}, …, f_{t_{i}−1}) = \frac{A(f, G_{t,i}(σ))}{A(f, t_{i})} .

Lemmas 30 and 11 together give a high-probability lower bound on A(f, G_{t,i}). By induction, we also have a highprobability upper bound on A(f, t_{i}). In other words, if we condition on the “good” event that both of these bounds hold, then the expectation in question is upper bounded by \frac{ke^{−(i+Δ)/k}−ϵ′Δ}{(1+η_{j})ke^{−Δ/k}} ≤ e^{−i/k}/(1 + η_{j}) + ϵ′′. Since X_{1}, …, X_{i−1} are functions of f_{0}, f_{1}, …, f_{t_{i}−1}, we have shown, for each i, that

E ( X_{i} | X_{0}, …, X_{i−1}, G_{i}) ≥ e^{−i/k}/(1 + η_{j}) + ϵ′′,

from which it follows by Theorem 27 that with high probability,

k − A(f, t) = ∑_{i=1}^{Δ} X_{i}
> ∑ e^{−i/k}/(1 + η_{j}) + ϵ′′′Δ
> k(1 − e^{−Δ/k})/(1 + η_{j}) + ϵ′′′′Δ.

Equivalently, with high probability,

A(f, t) < k ( \frac{e^{−Δ/k} + η_{j}}{1 + η_{j}} + ϵ^{(5)}) .

Setting this upper bound equal to (1+η_{j+1})ke^{−Δ/k}, we find

η_{j+1} ≤ \frac{η_{j}(e^{Δ/k} − 1)}{1 + η_{j}} + ϵ^{(6)}e^{Δ/k}.

Since e^{Δ/k} − 1 < 1 for k > 1.45Δ, the sequence η_{0}, η_{1}, … decreases essentially geometrically, until it reaches the same order of magnitude as ϵ′′. Choosing ϵ′′ sufficiently small allows the desired goal of η_{C/C′} = ϵ. We omit the details of what each “high probability” means, as well as the relationships between the various ϵ’s.

Our next result says, roughly, that if we were to randomly select a neighbor of v, and recolor it with a legal color, then every color (except that of v) is about equally likely to be chosen. Equivalently, every color is about equally likely to be forbidden (ignoring v).

Lemma 31. For every ϵ > 0, there exists C > 0 such that for every time t > Cn, color c ∈ [k], and Δ-regular graph G having girth ≥ 6 and degree Δ ≥ C log n, when f = (f_{0}, …, f_{T}) is selected according to Glauber dynamics,

|{w ∈ Γ(v) : c ∈ Γ(w) \ {v}}| ∈ [Δ(1 − e^{−Δ/k}) ± ϵΔ].

We omit the proof, which is another iterative argument in the style of the proof of Lemma 30. The final step in our sketch is to show that, if a random neighbor of v is chosen, then every pair of colors is about equally likely to be forbidden. This is a key property, since it means that when two coupled copies of Glauber dynamics differ at v, only a certain fraction of the neighbors of v are at risk to propagate this difference.

Lemma 32. For every ϵ > 0, there exists C > 0 such that for every time t > Cn, colors c, c′ ∈ [k] and Δ-regular graph G having girth ≥ 6 and degree Δ ≥ C log n, when f = (f_{0}, …, f_{T}) is selected according to Glauber dynamics,

|{w ∈ Γ(v) : c, c′ ∈ Γ(w) \ {v}}| ∈ [Δ(1 − e^{−Δ/k})^{2} ± ϵΔ].

Once Lemma 32 has been established, Theorem 2 follows by a coupling argument very similar to Theorem 14. See the full version for details.

7. RANDOM GRAPHS

Theorem 3 follows easily from the following fact.

Proposition 33. Let G be a random graph on n vertices with edges included independently with probability p. Let Δ denote the maximum degree of G. Then, for every ϵ ∈ [0, 1],

Pr (|Δ − pn| > ϵpn) ≤ ne^{−ϵ^{2}pn/3}.

For ℓ ≥ 3, let X_{ℓ} denote the maximum over all v, of the number of neighbors of v contained in a cycle of length ≤ ℓ through v. Then

Pr (X_{ℓ} > ϵpn) < n^{O(1)} (p^{ℓ}n^{ℓ−1})^{Ω(ϵpn)} .

Thus choosing p = Ω(log n) ensures that Δ = Ω(log n) with high probability, and choosing p < n^{−1+1/ℓ−ϵ} ensures that G has too few short cycles of length ≤ ℓ to interfere with any of the arguments from this paper. In particular, setting ℓ = 4 and ℓ = 5, and applying Theorems 1 and 2 implies Theorem 3 for the independent-edges model. The extension to random regular graphs follows by similar methods.

8. ACKNOWLEDGEMENTS

I would like to thank Eric Vigoda for introducing me to the area, and for many, many helpful discussions. Thanks also to my advisor Laci Babai, and to all the theory group at the University of Chicago, for much encouragement and patient listening.

9. REFERENCES

[1] G. Brightwell and P. Winkler. Random colorings of a Cayley tree. In B. Bollobás, editor, Contemporary Combinatorics, volume 10 of Bolyai Society Mathematical Studies. Springer Verlag, 2002.

[2] R. Bubley and M. Dyer. Path coupling: a technique for proving rapid mixing in Markov chains. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pages 223–231. IEEE, October 1997.

[3] D. Dubhashi. Simple proofs of occupancy tail bounds. Random Structures and Algorithms, 11(2):119–123, 1997.

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

[5] 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, pages 579–587. IEEE, October 2001.

[6] M. Dyer, C. Greenhill, and M. Molloy. Very rapid mixing of the Glauber dynamics for proper colourings on bounded-degree graphs. Random Structures and Algorithms, 20:98–114, 2002.

[7] T. Hayes. Randomly coloring bipartite graphs. Manuscript, in progress, 2003.

[8] T. Hayes and E. Vigoda. A non-Markovian coupling technique. Technical Report TR-2003-02, University of Chicago, February 2003.

[9] M. Jerrum. A very simple algorithm for estimating the number of k-colourings of a low-degree graph. Random Structures and Algorithms, 7:157–165, 1995.

[10] M. Jerrum, L. Valiant, and V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169–188, 1986.

[11] 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, pages 91–98, 2002.

[12] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, Cambridge, 1995.

[13] J. Salas and A. Sokal. Absence of phase transition for anti-ferromagnetic Potts models via the Dobrushin uniqueness theorem. Journal of Statistical Physics, 86:551–579, 1997.

[14] E. Vigoda. Improved bounds for sampling colorings. J. Math. Phys., 41:155–169, 2000.