Shai Vardi
email: svardi@caltech.edu.

Randomly coloring

Introduction

A (proper) k-coloring of a graph G = (V, E) is an assignment σ : V → {1, . . . , k} such that neighboring vertices have different colors. We consider the problem of sampling (almost) uniformly at random from the space of all k-colorings of a graph. 1 The problem has received considerable attention from the computer science community in recent years, e.g., [START_REF] Dyer | Randomly coloring random graphs[END_REF]17,[START_REF] Hayes | A non-markovian coupling for randomly sampling colorings[END_REF][START_REF] Jerrum | A very simple algorithm for estimating the number of k-colorings of a lowdegree graph[END_REF][START_REF] Lu | An FPTAS for counting proper four-colorings on cubic graphs[END_REF][START_REF] Tetali | Phase transition for the mixing time of the Glauber dynamics for coloring regular trees[END_REF][START_REF] Vigoda | Improved bounds for sampling colorings[END_REF]. It also has applications in Combinatorics (e.g., [START_REF] Brightwell | Random coloring of a Cayley tree[END_REF]) and Statistical Physics (e.g., [START_REF] Salas | Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem[END_REF]).

Sampling colorings (as well as other combinatorial objects, e.g., [6,[START_REF] Jerrum | Approximating the permanent[END_REF][START_REF] Morris | Random walks on truncated cubes and sampling 0-1 knapsack solutions[END_REF]) is commonly done using Markov Chain Monte Carlo (MCMC) methods. A large body of work on sampling colorings is devoted to analyzing a particular Markov chain, known as Glauber dynamics: Choose a vertex v uniformly at random; choose a color c uniformly at random from the set of available colors (the complement of the set of colors of the neighbors of v); recolor v with c. Jerrum [START_REF] Jerrum | A very simple algorithm for estimating the number of k-colorings of a lowdegree graph[END_REF] showed that the Glauber dynamics mix in time O(n log n) when k > 2∆, where ∆ is the maximal degree of the graph. Vigoda [START_REF] Vigoda | Improved bounds for sampling colorings[END_REF] improved the bound on the number of colors to k > 11∆/6 using a different Markov chain, and showed that it mixes in time O(nk log n). This remains the best known bound on k for general graphs. A major open question is for what values of k can we sample colors efficiently (i.e., in polynomial time)? It is conjectured (e.g., [START_REF] Brightwell | Counting linear extensions is #P-complete[END_REF]) that k = ∆ + 2 colors suffice, and furthermore, that the Glauber dynamics mix rapidly for any k ≥ ∆ + 2.

A lot of work has focused on improving the bounds of Vigoda on restricted families of graphs. Dyer and Frieze [START_REF] Dyer | Randomly coloring graphs with lower bounds on girth and maximum degree[END_REF] showed that if the maximal degree and girth are Ω(log n), the Glauber dynamics mix in O(n log n) for k > α∆, where α ≈ 1.763. The degree and girth requirements and the value of α were improved in a line of works [START_REF] Dyer | Randomly coloring constant degree graphs[END_REF][START_REF] Hayes | Randomly coloring graphs of girth at least five[END_REF][START_REF] Hayes | A non-markovian coupling for randomly sampling colorings[END_REF][START_REF] Hayes | Coupling with the stationary distribution and improved sampling for colorings and independent sets[END_REF]36]; see Table 1 for a comparison and summary of some milestones. The current state of the art results exhibit a tradeoff between the value of α and the degree and girth requirements. Hayes and Vigoda [START_REF] Hayes | A non-markovian coupling for randomly sampling colorings[END_REF] showed that on graphs with ∆ = Ω(log n) and girth at least 9, (1 + )∆ colors suffice to ensure fast mixing. On the other hand, the Glauber dynamics have been shown to mix rapidly on graphs with girth at least 5 (resp. 6) and ∆ > ∆ 0 (where ∆ 0 is some absolute constant) using roughly 1.763∆ (resp. 1.489∆) colors [START_REF] Dyer | Randomly coloring constant degree graphs[END_REF]. Stronger bounds have only been shown on highly specialized families of graphs, such as trees [START_REF] Martinelli | Fast mixing for independent sets, colorings and other models on trees[END_REF], planar graphs [START_REF] Hayes | Randomly coloring planar graphs with fewer colors than the maximum degree[END_REF], Erdös-Rényi graphs [START_REF] Dyer | Randomly coloring random graphs[END_REF] and cubic graphs [START_REF] Lu | An FPTAS for counting proper four-colorings on cubic graphs[END_REF].

The two results that are closest to ours are the following: Hayes [START_REF] Hayes | A simple condition implying rapid mixing of single-site dynamics on spin systems[END_REF] showed that if for graphs with maximum eigenvalue ρ, the mixing time of the Glauber dyanmics is O(n log n), when k > ∆ + cρ, where c is slightly greater than 1. Planar graphs, trees and graphs of bounded treewidth have a maximum eigenvalue of O( √ ∆), implying fast mixing for these graphs. Berger et al. [START_REF] Berger | Glauber dynamics on trees and hyperbolic graphs[END_REF] showed that for graph with bounded degree and logarithmically bounded cutwidth, the Glauber dynamics mix in polynomial time. We formally define treewidth, pathwidth and cutwidth later on, but we note that the pathwidth of any graph G is at least as large as its cutwidth, which is at least as large as its treewidth. In addition, the pathwidth is at most O(log n) times the treewidth.

Results and Techniques

Our main result is an algorithm that efficiently samples a ((1 + )∆)-coloring (almost) uniformly at random if the input graph has logarithmically bounded pathwidth, for any > 0.

[45] Ω(log n) Ω(log n) any (1.763 . . .)∆ Glauber O(n log n) [11] Ω(log n) ≥ 9 any (1 + )∆ Glauber O(n log n) [24] ≥ ∆ 0 † ≥ 5 any (1.763 . . .)∆ Glauber O(n log n) [13] ≥ ∆ 0 † ≥ 6 any (1.489 . . .)∆ Glauber O(n log n) [13] O(1)
∞ Trees 4 Glauber poly(n) [START_REF] Lucier | The Glauber dynamics for colorings of bounded degree trees[END_REF] any any treewidth= O(1)

∆ + Ω √ ∆ Glauber poly(n) [21] O(1) any cutwidth= O(log n) ∆ + 2 Glauber poly(n) [2] any any pathwidth = O(log n) (1 + )∆ Single-Flaw poly(n)
Here † ∆ 0 is some absolute constant.

Theorem 1.1. (Informal) Let > 0 and G be a graph with n vertices and maximal degree ∆.

There exists an algorithm for sampling a ((1 + )∆)-proper coloring of G (almost) uniformly at random, whose running time is polynomial in n, ∆, and -O(pw(G)) , where pw(G) is the pathwidth of G. In particular, when pw(G) = O(log n), the algorithm runs in polynomial time.

The two main methods of bounding the mixing time of random walks are coupling and bounding the spectral gap of the transition matrix [START_REF] Guruswami | Rapidly mixing markov chains: A comparison of techniques (A survey)[END_REF]; methods of bounding the conductance or congestion (which are used to bound the spectral gap) are generally considered to be stronger than coupling methods [START_REF] Guruswami | Rapidly mixing markov chains: A comparison of techniques (A survey)[END_REF][START_REF] Kumar | Coupling vs. conductance for the jerrum-sinclair chain[END_REF]. Despite this, most of the work on sampling colorings uses various coupling methods [START_REF] Dyer | Randomly coloring sparse random graphs with fewer colors than the maximum degree[END_REF][START_REF] Dyer | Randomly coloring graphs with lower bounds on girth and maximum degree[END_REF][START_REF] Dyer | Randomly coloring random graphs[END_REF][START_REF] Dyer | Randomly coloring constant degree graphs[END_REF][START_REF] Hayes | Randomly coloring graphs of girth at least five[END_REF][START_REF] Hayes | Randomly coloring planar graphs with fewer colors than the maximum degree[END_REF][START_REF] Hayes | Randomly coloring planar graphs with fewer colors than the maximum degree[END_REF][START_REF] Hayes | A non-markovian coupling for randomly sampling colorings[END_REF][START_REF] Hayes | Coupling with the stationary distribution and improved sampling for colorings and independent sets[END_REF][START_REF] Jerrum | A very simple algorithm for estimating the number of k-colorings of a lowdegree graph[END_REF]36,[START_REF] Vigoda | Improved bounds for sampling colorings[END_REF]; the Glauber dynamics do not lend themselves easily to the techniques that are usually used for bounding the spectral gap. In particular, bounding the congestion of the underlying graph of the transition matrix3 typically involves defining flows between states in the underlying graph. If one can describe a flow in the underlying graph such that the congestion of each edge is not too large, it implies that the spectral gap is large and the Markov chain mixes rapidly [START_REF] Diaconis | Geometric bounds for eigenvalues of markov chains[END_REF]43]. It is not clear how to construct such flows for the Glauber dynamics, as a transition involves changing a vertex's color to one of its available colors: if all of the neighbors of a vertex v that is colored blue are colored red, how do we go about changing v's color to red?

We introduce a new Markov chain, which we call Single-Flaw dynamics. The difference between the Single-Flaw and Glauber dynamics is that the Single-Flaw dynamics also allow colorings that have a "single flaw" -there is at least one monochromatic edge, and all monochromatic edges share a vertex. In other words, the coloring is not proper, but there is a single vertex v such that we can reach a proper coloring by changing v's color only. We call such colorings singly-flawed. Concretely, the Single-Flaw dynamics Markov chain is the following: choose a vertex v and a color c at random. If changing v's color to c results in a coloring that is either proper or singly-flawed, change v's color to c. Otherwise do not.

The main advantage afforded by this Markov chain is that it allows us to define paths between two states (colorings) α and β: select some order on the vertices, v 1 , . . . , v n . Starting from v 1 , for each vertex v i , change its color to β(v i ). If the transition leads to a proper coloring, continue to v i+1 . Otherwise, "fix" the monochromatic edges by recoloring the neighbors of v i that are also colored β(v i ) (as k ≥ ∆ + 1 there is always at least one available color). When there are no monochromatic edges remaining, continue to vertex v i+1 . We note that it is possible to first "fix" the neighbors of v and only then change the color of v, and this corresponds to the Glauber dynamics; we only lose a single color choice per neighbor (in the Single-Flaw dynamics we can recolor with the original color of v, whereas in the Glauber dynamics we cannot). Therefore, our analysis can be easily modified to apply to the Glauber dynamics. We chose to analyze the Single-Flaw dynamics for two reasons (in addition to using one fewer color): 1) The analysis is cleaner this way, and 2) It is straightforward to extend the analysis techniques to "Multi-Flaw" dynamics, which we believe could prove useful in other sampling and counting settings as well.

We first describe a simple attempt to adapt the canonical paths argument of Jerrum and Sinclair [START_REF] Jerrum | Approximating the permanent[END_REF][START_REF] Jerrum | A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries[END_REF] to our setting, using the canonical paths described above. Although it fails in all non-trivial cases, it is instructive as it exemplifies an important part of our method. For every edge in the underlying graph, (try to) describe an injective function from paths going through the edge to the state space of the chain. If we can describe such a function, it would mean that at most |Ω| paths use each edge. If there were no "fixing phase" (i.e., the graph was disconnected), this would be easy: Let t be the transition from the state σ such that the color of the j th vertex is changed to c. The injective function would map the path from α to β to the following coloring σ * : for vertices v i : i = 1, 2, . . . j, σ * = α(v i ), for all other vertices v i : i

= j + 1, . . . , n, σ * (v i ) = β(v i ).
The mapping is injective because (i) σ * a proper coloring and (ii) knowing t and σ * allows us to recover α and β, as

σ(v i ) = β(v i ) i = 1, 2, . . . , j α(v i ) otherwise.
This would imply that at most |Ω| paths would use each transition. We note that it is not necessary to show that at most |Ω| paths use each transition to show polynomial time mixing; it suffices to show that |Ω| • poly(n) paths use each transition [START_REF] Jerrum | Approximating the permanent[END_REF]. If we are guaranteed that at every round, at most r vertices will be colored differently from α and β, this means that at most

(k -1) r |Ω| (1)
paths use each transition. This observation was used by Berger et al. [START_REF] Berger | Glauber dynamics on trees and hyperbolic graphs[END_REF], who used the cutwidth to bound r. (The cutwidth of a graph G is the smallest integer r such that there exists a labeling v 1 , . . . , v n of the vertices such that for all 1 ≤ k ≤ n, the number of edges from {v 1 , . . . , v k } to {v k+1 , . . . , v n } is at most r.) We use a similar argument, but are able to leverage the pathwidth of the graph, which gives a stronger result, as the pathwidth of any graph is at least as large as its cutwidth. In essence, a small pathwidth implies that there is some order on the vertices, such that if our canonical paths obey this order, not too many vertices will need to be fixed at any time. We note that finding such an order is N P -hard [START_REF] Bodlaender | Approximating treewidth, pathwidth, frontsize, and shortest elimination tree[END_REF], however we only need that such an order exists for the canonical paths argument.

The main contribution in this paper is removing the requirement that the maximal degree is bounded by a constant; in other words, removing the number of colors from the base in Expression [START_REF] Aldous | Random walks on finite groups and rapidly mixing markov chains[END_REF]. In order to do this, we use a multicommodity flow argument [START_REF] Diaconis | Geometric bounds for eigenvalues of markov chains[END_REF]43]. Instead of specifying a single path for each pair of states, we describe a flow between them in the underlying graph. Whenever we fix a vertex's color, we split the flow evenly among all available options. This is similar to the argument of Morris and Sinclair [START_REF] Morris | Random walks on truncated cubes and sampling 0-1 knapsack solutions[END_REF], in which flow is also split up among different paths; it helps route the flow more evenly, thereby avoiding the case where one edge is heavily congested while other "available" edges are not. In contrast to [START_REF] Morris | Random walks on truncated cubes and sampling 0-1 knapsack solutions[END_REF], we only split the flow in the fixing stages; in fact, whenever a vertex v i is colored β(v i ), this consolidates the flow! Our technique can be thought of as a hybrid argument between the canonical paths proof technique of [START_REF] Jerrum | Approximating the permanent[END_REF] and the multicommodity flow argument of [START_REF] Morris | Random walks on truncated cubes and sampling 0-1 knapsack solutions[END_REF]. We call these paths hybrid paths and believe they could be useful in other scenarios as well.

Finally, recall that the state space of the Single-Flaw dynamics includes flawed colorings. We show that there are not too many singly-flawed colorings relative to proper colorings, hence executing the chain polynomially many times will guarantee that we output a proper coloring w.h.p.

Related work

Most of the work on sampling colorings has focused on the Glauber dynamics (e.g., [START_REF] Dyer | Randomly coloring random graphs[END_REF][START_REF] Dyer | Randomly coloring constant degree graphs[END_REF]17,[START_REF] Hayes | Randomly coloring planar graphs with fewer colors than the maximum degree[END_REF][START_REF] Jerrum | A very simple algorithm for estimating the number of k-colorings of a lowdegree graph[END_REF][START_REF] Lu | An FPTAS for counting proper four-colorings on cubic graphs[END_REF][START_REF] Lucier | The Glauber dynamics for colorings of bounded degree trees[END_REF]36,[START_REF] Mossel | Gibbs rapidly samples colorings of g(n, d/n)[END_REF][START_REF] Tetali | Phase transition for the mixing time of the Glauber dynamics for coloring regular trees[END_REF]). Other Markov chains have been analyzed, notably the Flip dynamics of Vigoda [START_REF] Vigoda | Improved bounds for sampling colorings[END_REF], which is closely related to the chain proposed by Wang, Swendsen, and Kotecký [START_REF] Wang | Antiferromagnetic potts models[END_REF]: when a vertex v is required to change color from c to c , the colors of the entire neighborhood that is colored with c and c are flipped (the chain of Vigoda only performs some flips with some probability). It is also possible to sample colorings using approaches that do not use MCMC methods; for example, Efthymiou [START_REF] Efthymiou | A simple algorithm for sampling colorings of g(n, d/n) up to the gibbs uniqueness threshold[END_REF] proposed a combinatorial method for sampling colors that does not use a Markov chain, and used it to show that it is possible to sample colorings on G(n, d/n) using k > (1 + )d colors. A caveat is that the run time is only polynomial w.p. 1 -2n -2/3 . The main difference between Single-Flaw dynamics and other work on sampling colors is that we allow improper states. There are other Markov chains that also consist of "flawed" states that are not part of the space we wish to sample from. An example is the Markov chain for sampling perfect matchings in bipartite graphs, proposed by Broder [7] and analyzed by Jerrum and Sinclair [START_REF] Jerrum | Approximating the permanent[END_REF] and Jerrum, Sinclair and Vigoda [START_REF] Jerrum | A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries[END_REF]: the chain consists of perfect matchings (of size n), and imperfect matchings of size n -1. An interesting distinction is that Broder's chain needs the imperfect matchings to transition between perfect matchings (otherwise, it is unclear how to transition). We do not need the imperfect states to show convergence: the Glauber dynamics are known to converge to the uniform distribution for k ≥ ∆ + 2; we only use the imperfect colorings to bound the mixing time. We do get the additional benefit that the Single-Flaw dynamics are guaranteed to converge for k ≥ ∆ + 1 (in contrast to the Glauber dynamics, which are not-a simple counterexample is a triangle graph); we do not leverage this in this work.

The method of bounding the conductance or congestion of the transition matrix of a Markov chain has been used to great success in sampling and counting of various problems e.g., [START_REF] Guo | Random cluster dynamics for the ising model is rapidly mixing[END_REF][START_REF] Jerrum | A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries[END_REF][START_REF] Morris | Random walks on truncated cubes and sampling 0-1 knapsack solutions[END_REF]. To our knowledge, the only places that these types of arguments have been successfully applied to sampling colorings is in bounding the mixing time of the Glauber dynamics on trees with bounded degree [START_REF] Lucier | The Glauber dynamics for colorings of bounded degree trees[END_REF] and hyperbolic graphs [START_REF] Berger | Glauber dynamics on trees and hyperbolic graphs[END_REF]. The arguments of [START_REF] Lucier | The Glauber dynamics for colorings of bounded degree trees[END_REF] and [START_REF] Berger | Glauber dynamics on trees and hyperbolic graphs[END_REF] both rely heavily on the upper bound on the degree and it does not appear possible to extend their techniques to more general settings.

Sampling colorings corresponds to sampling configurations of the zero temperature k-state antiferromagnetic Potts model [START_REF] Potts | Some generalized order-disorder transformations[END_REF]. One can draw an analogy between our technique and temperaturetuned walks that also include higher energy levels (see e.g., [START_REF] Jun | Monte Carlo Strategies in Scientific Computing[END_REF]), though instead of walking at a fixed temperature, which would allow some Poisson-like distribution of the number of flaws, we allow exactly one flaw, and correct it before allowing the next flaw.

The terms treewidth and pathwidth were introduced by Robertson and Seymour [START_REF] Robertson | Graph minors. i. excluding a forest[END_REF][START_REF] Robertson | Graph minors. iii. planar tree-width[END_REF]; the concept of treewidth was discovered independently several times, and was originally introduced under a different name by Bertelè and Brioschi [START_REF] Bertelè | Nonserial Dynamic Programming[END_REF]. Of particular interest is a work by Chekuri, Khanna and Shepherd [START_REF] Chekuri | A note on multiflows and treewidth[END_REF] that consider multicommodity flows on graphs of bounded treewidth.

Their techniques and results are incomparable to ours; they study the flow on graphs, while we use a flow to bound the congestion on the underlying graph of the Single-Flaw dynamics.

Preliminaries

We denote the set {1, 2, . . . , m} by [m]. Let G = (V, E) be a graph, and denote |V | = n. We assume that the vertices of G are uniquely identified by {1, 2, . . . , n}. For any (not necessarily simple) path p in G, let |p| denote the length of p (i.e., the number of edges in p, where if an edge appears k times in p, it is counted k times).

Colorings

For any k-coloring of G, σ : V → [k], let M CE(G) = {(u, v) : σ(u) = σ(v)} denote the set of monochromatic edges. σ is a proper coloring if M CE(G) = ∅. σ is a singly-flawed coloring if M CE(G) = ∅
and there is a vertex that is common to all edges in M CE(G), i.e., ∃v : ∀e ∈ M CE(G), v ∈ e. We say that such a vertex v is a flawed vertex of σ. Note that a singly-flawed coloring has exactly two flawed vertices if |M CE(G)| = 1 and one flawed vertex otherwise. We denote the set of proper k-colorings of G colors by C p (G, k) and the set of all singly-flawed colorings by C sf (G, k). We drop G and k when they are clear from context. Let σ be a coloring. If, after recoloring some v ∈ V with a color c, there is no monochromatic edge (u, v), we say that c is available to v in σ. Note that a color's availability does not depend on whether σ or the coloring obtained by recoloring v with c is proper, singly-flawed or otherwise.

We first show two results that will be useful later on, regarding proper and singly-flawed colorings: (1) the ratio of singly-flawed colorings to proper colorings is "not too large" (Corollary 2.2), and (2) there is a mapping from singly-flawed colorings to proper colorings, such that "not too many" singly-flawed colorings are mapped to any proper coloring (Corollary 2.3). Both results are corollaries of the following simple lemma.

C p (G, k) × [k] × [n] → C sf (G, k).
Proof. For every coloring σ ∈ C p (G, k), every vertex v ∈ V and every color c

∈ [k], let σ c,v = σ(u) if u = v c if u = v If σ c,v ∈ C sf (G, k), let g(σ, c, v) = σ c,v , otherwise let g(σ, c, v) be some arbitrary coloring in C sf (G, k). It is easy to see that every σ ∈ C sf (G, k
) is in the range of g: the reverse operation of changing the color of a flawed vertex v in σ to some available color gives a proper coloring.

The two corollaries that we require are the following.

Corollary 2.2. For any G = (V, E) such that |V | = n and k ≥ ∆ + 2, |C sf (G, k)| ≤ kn|C p (G, k)|.
Proof. Immediate from the surjectivity of the function g in Lemma 2.1.

Corollary 2.3. For any G = (V, E) such that |V | = n and k ≥ ∆ + 2, there exists a function

g : C sf (G, k) → C p (G, k),
for which each element in the co-domain has at most kn pre-images in the domain.

Proof. For every σ ∈ C sf , arbitrarily select one pre-image (σ, v, c) w.r.t. g, and set σ as the image for σ under g .

Markov chains and rapid mixing

In this section we review some of the results on the mixing time of Markov chains that we will require. The reader is referred to [START_REF] Levin | Markov chains and mixing times[END_REF] for an excellent introduction to Markov chains and modern techniques on bounding their mixing time. Consider a discrete-time Markov chain MC with finite state space Ω and symmetric transition probability matrix P (i.e., P (σ, σ ) = P (σ , σ) for all σ, σ ∈ Ω). The chain is said to be irreducible if for every pair of states σ, σ ∈ Ω, there exists some t such that P t (σ, σ ) > 0; in other words, it is possible to get from any state to any state using a finite number of transitions. It is aperiodic if for any σ, ∈ Ω, gcd{t : P t (σ, σ) > 0} = 1. It is lazy if for all σ ∈ Ω, P (σ, σ) > 1/2. A fundamental theorem of stochastic processes states that an irreducible and aperiodic Markov chain converges to a unique stationary distribution π over Ω, i.e., lim t→∞ P t (σ, σ ) = π(σ ) for all σ, σ ∈ Ω. If in addition P is symmetric, then π is uniform over Ω (e.g., [START_REF] Aldous | Random walks on finite groups and rapidly mixing markov chains[END_REF]).

Our goal is to describe a fully-polynomial almost uniform sampler for proper colorings; namely, a randomized algorithm that, given as inputs a graph G = (V, E) and a bias parameter δ, outputs a random proper coloring of G from a distribution D that satisfies d T V (D, U ) ≤ δ, where U is the uniform distribution on the proper colorings of G and d T V is the total variation distance, defined as follows: 4 For any two distributions µ, ν on Ω,

d T V (µ, ν) = max S⊆Ω |µ(S) -ν(S)|.
(

) 2
We are interested in the rate at which a Markov chain converges to its stationary distribution π. We define the mixing time from a state σ to be

τ σ (δ) = min{ t : d T V (P t (σ, •), π) ≤ δ for all t ≥ t}, (3)
We further define the mixing time of the Markov chain to be τ (δ) = max σ τ σ (δ). We say that a Markov chain is rapidly mixing if τ (1/2e) is polynomial in n. The constant 1/2e is arbitrary, as a bound on τ (1/2e) implies a bound on τ (δ) for any δ > 0 (e.g., [START_REF] Aldous | Random walks on finite groups and rapidly mixing markov chains[END_REF]):

τ (δ) ≤ (1 -log δ) • τ (1/2e).
In order to bound the mixing time, we describe a multicommodity flow on the underlying graph H = (Ω, F ) of the Markov chain, where F = {(σ, σ ), P (σ, σ ) > 0} is the set of all transitions that have positive probability.

We denote by q(σ, σ ) = π(σ)P (σ, σ ),

the ergodic flow through the edge (σ, σ ) of H (an intuitive way to think about q(σ, σ ) is the probability of traversing edge (σ, σ ) at stationarity.) For all ordered pairs (α, β) ∈ Ω 2 , let P α,β denote a set of (not necessarily simple) directed paths from α to β in H. A flow is a function f : P → R + ∪ {0} where P = α,β P α,β that satisfies

f α,β ≡ p∈P α,β f (p) = π(α)π(β), (5)
for every α, β ∈ Ω. We define the congestion on an edge (σ, σ ) with respect to a flow f by

ρ f (σ, σ ) = 1 q(σ, σ ) α,β∈Ω p:(σ,σ )∈p∈P α,β f (p)|p|, (6)
and the congestion of f by

ρ f = max (σ,σ )∈F ρ f (σ, σ ).
We use the following theorem, due to Sinclair [43] and Diaconis and Stroock [START_REF] Diaconis | Geometric bounds for eigenvalues of markov chains[END_REF], that relates the mixing time to the congestion of a flow. Note that it holds for any flow; in order to bound the mixing time, we need to find some flow that has low congestion.

Theorem 2.4.

[43] For any irreducible, aperiodic, lazy and symmetric Markov chain MC with transition matrix P on state space Ω, any flow f on the underlying graph of MC, and any state

σ 0 ∈ Ω, τ σ 0 (δ) ≤ ρ f ln π(σ 0 ) -1 + ln δ -1 .

Pathwidth and vertex separation

A path decomposition of a graph G = (V, E) is a path P with m nodes, where each node of P represents a subset of V : X i ⊆ V, i ∈ [m] such that the following hold:

1. m i=1 X i = V , 2. For every (u, v) ∈ E, u, v ∈ X i for some i ∈ [m].
3. For all i, j, k ∈ [m], if X j is on the (unique) path between X i and X k , then

X i ∩ X k ⊆ X j .
The first requirement guarantees that every vertex of G is in at least one node of P , the second that every two neighboring vertices in G share at least one node in P , and the third that if some vertex v ∈ V is in both X i and X k , it is in every node of the path between X i and X k in P . The width of P is defined as max i∈[m] {|X i | -1}. The pathwidth of G, denoted pw(G), is the minimal ω such that there exists some path-decomposition of G with width ω. The treewidth is similarly defined, when P is a tree. A linear ordering of a graph G = (V, E) is a bijective mapping of vertices to integers; L : V → {1, 2, . . . , n}. Given a graph G, a linear ordering L, and an integer j ∈ {1, . . . , n}, let A j be the set of vertices mapped to the integers 1, . . . , j by L; i.e., A j = {v : L(v) ≤ j}. Let B j denote the set of vertices that are mapped to integers greater than j by L: B j = V \ A j . A minimal vertex separator for an index j ∈ {1, . . . n} (denoted MVS(G, L, j)) is a minimal set of vertices S j ⊂ V such that the following hold: 51. For all u ∈ S j , L(u) > j.

2. A j and B j \ S j are disconnected; that is, there is no edge (u, v) ∈ E such that u ∈ A j , v ∈ B j \ S j .

W.l.o.g., we henceforth assume for simplicity that L is the identity ordering; i.e., ∀j ∈ {1, . . . , n}, L(j) = j.

The vertex separator number for a graph G, denoted VSN(G) is the minimal size of the largest minimal vertex separator over all possible linear orderings L of G.

VSN(G) = min L max j∈{1,...,n} {MVS(G, L, j)}.
We call an order L for which VSN(G) is minimized a minimal order for G.

We require the following claim and theorem.

Claim 2.5. Let G and L be a graph and a linear order thereof. For j = 1, . . . , n, set S j = MVS(G, L, j). For all j ∈ {2, . . . , n}, S j-1 ⊆ S j ∪ {j}.

Proof. For any j ∈ {1, . . . , n}, S j is uniquely determined: it is exactly the neighbors of the vertices of A j in B j . This is because for every v ∈ A j , the set N (v) ∩ B j must all be in S j , otherwise there is an edge between v and B j . From the minimality of S j , therefore, S j = v∈A j N (v) ∩ B j . Hence,

• If j ∈ S j-1 then S j = S j-1 \ {j} ∪ (N (j) ∩ B j ). • If j / ∈ S j-1 then S j = S j-1 ∪ (N (j) ∩ B j ).
This completes the proof of the claim.

Theorem 2.6. [START_REF] Kinnersley | The vertex separation number of a graph equals its path-width[END_REF] For any graph G, VSN(G) = pw(G).

Single-Flaw dynamics

Let G = (V, E) be a graph with maximal degree ∆ and > 0 such that (1 + )∆ ≥ ∆ + 2. The state space Ω of Markov chain MC(G, ) (or simply MC) is the set of all proper and singly-flawed

k-colorings of G, for k = (1 + )∆ : Ω = C p (G, k) ∪ C sf (G, k).
For simplicity, we henceforth assume that ∆, (1 + )∆ and (1 + ) -1 are integers. It is easy to generalize the results to real values thereof. For σ ∈ Ω, the transitions σ → σ of MC are the following

• Let σ = σ.
• With probability 1/2, do nothing (laziness).

• Otherwise, choose a vertex v and color c uniformly at random from V and [k] respectively. Tentatively, set σ (v) = c.

• If σ / ∈ Ω, set σ (v) = σ(v).
It is easy to verify that the chain is irreducible, aperiodic, lazy and symmetric; hence the conditions of Theorem 2.4 hold, and it remains to describe a flow with low congestion of the underlying graph of MC. Our main result describes such a flow. Lemma 3.1. Let > 0 and G be a graph with maximal degree ∆. Then there exists a flow f on the underlying graph of the Markov chain MC(G, ) such that

ρ f ≤ 8 pw(G)(1 + ) 3 ∆ 3 n 5 (1 + ) -1 2 pw(G) .
There are at most k n possible colorings of G. Because the stationary distribution is uniform, for all σ ∈ Ω, π(σ) ≥ 1 k n , hence ln π(σ) -1 = O(n log n). Theorem 2.4 and Lemma 3.1 imply the following theorem, which is our main result. Theorem 3.2. Let > 0 and G be a graph with maximal degree ∆. The mixing time of MC(G, )

satisfies τ (δ) = O pw(G)(1 + ) 3 ∆ 3 n 5 (1 + ) -1 2 pw(G) n log n + ln δ -1 .
In particular, if pw(G) = O(log n), the chain mixes in polynomial time.

In order to prove Lemma 3.1, we design a flow for MC. To do so, we first describe the set of paths that we will route the flow through.

Hybrid paths

Let L be some minimal order of G. For simplicity and w.l.o.g. we assume that L is the identity order, i.e., L(i) = i for all i ∈ [n]. We remark that we do not need to explicitly find L; we only require its existence for the hybrid paths argument. Let λ = VSN(G) log n . If pw(G) = O(log n), as is assumed here, λ is a constant.

For each j ∈ [n], let S j = MVS(G, L, j) be a minimal vertex separator. We denote the set of hybrid paths from α to β by γ α,β . For the rest of this subsection and the next, we assume that α and β are both proper colorings; we will extend the sets of paths to include ones that start and/or end at singly-flawed colorings in Section 3.3. We divide each path into n phases, where phase j consists of |S j | + 1 steps, for a total of = n + n j=1 |S j | ≤ (λ + 1)(n log n) steps. Each step is a recoloring of some vertex; it is possible that a vertex is "recolored" with the same color. In that case, the state (coloring) does not change, but we still count this redundant recoloring as a step, as it guarantees that all paths are of the same length; this will help to make the analysis more concise. A state that appears at the start of the th step of the j th phase of a hybrid path in γ α,β is said to be at distance (j, ) from α; alternatively, we say that it happens at time (j, ). We denote the states of γ α,β that are at distance (j, ) from α by Φ α,β (j, ). The set of hybrid paths γ α,β can be thought of as a layered graph, where all states of Φ α,β (j, ) are placed in the same layer.

A phase of the hybrid paths

We describe a single phase of γ α,β . For any j ∈ [n], all states in Φ α,β (j, 1) are proper colorings. Note that Φ α,β (1, 1) = {α}. For the first step of the j th phase, for every σ i ∈ Φ α,β (j, 1), set

σ i (v) = σ i (v) if v = j β(j) if v = j .
We therefore have that Φ α,β (j, 2) = i σ i . It is clear that there is only one way to route the flow entering σ i : it is all routed to σ i on (σ i , σ i ). It is possible that flow becomes consolidated in this step: the flow from all states σ i ∈ Φ α,β (j, 1) that differ only in the j th coordinate is routed to the same σ i . Note that every σ ∈ Φ α,β (j, 2) is either a proper or a singly-flawed coloring.

The th step in the j th phase, ∈ {2, 3, . . . |S j | + 1} is a splitting step, and is the following: Let u be the (lexicographically) ( -1) th vertex of S j . For every σ i ∈ Φ α,β (j, ), let C i (u ) be the set of colors available to u under σ i . For each σ i ∈ Φ α,β (j, ) and color c ∈ C i (u ), let

σ i,c (v) = σ i (v) if v = u c if v = u .
We have that Φ α,β (j, + 1) = i σ i,c . From each state σ i ∈ Φ α,β (j, ), the flow is split evenly among the transitions (i.e., a 1/|C i (u )| fraction of the flow entering σ i is routed on each (σ i , σ i,c )). Note that all states in Φ α,β (j, |S j | + 2) are proper colorings, as any edge that may have been monochromatic in any σ ∈ Φ α,β (j, 2) will have been recolored. For all 1

≤ j < n, set Φ α,β (j + 1, 1) = Φ α,β (j, |S j | + 2). Note that S n = ∅ and Φ α,β (n, 2) = {β}.
Because for all j, |S j | = O(log n), given α, β, j and , the color of most vertices in Φ α,β (j, ) is uniquely determined. In particular, for > 1, denote A j = {v : v ≤ j} and B j = V \ (A j ∪ S j ). 6It must hold that for any σ ∈ Φ α,β (j, ), v a ∈ A j , and

v b ∈ B j , σ(v a ) = β(v a ) and σ(v b ) = α(v b ).
This is because all the vertices in A j have been recolored to β and will not be recolored again, while the vertices in B j have no neighbors in A j , hence they have not been recolored yet.

We denote by QS(α, β, j, ) (QS stands for "quantum set") the number of vertices whose color is not uniquely defined by α, β, j, . By Claim 2.5, it holds that QS(α, β, j, ) ⊆ S j , but equality does not necessarily hold: assume that S j-1 ⊂ S j , and let u = j be some vertex in S j \ S j-1 . Then u's color is still α(u) at time (j, 2), as it has not yet been recolored, even though u ∈ S j .

We note that QS(α, β, j, ) does not in fact depend on α or β. In fact, Observation 3.3. QS(α, β, j, ) is uniquely determined by either 1. j and , or 2. j and (σ, σ ).

Proof. For any α, β, the same vertex is recolored at (j, ): at = 1, vertex j is recolored; in all other instances, u is recolored by at least ∆ different colors, regardless of α, β. Further, note that once a vertex u is in such a "quantum state", it will remain in quantum state until it is colored β(u) at distance (u, 1). Therefore, although we cannot recover the exact transitions used without knowledge of α, β, the set of vertices whose color is unknown at any given time is fixed.

For the second observation, notice that (σ, σ ) recolors some specific vertex u (even if it is an idle recoloring), hence can be inferred.

Due to Observation 3.3, we sometimes refer to QS(α, β, j, ) by QS(j, (σ, σ )) or QS(j, ).

Bounding the flow

Let α and β be proper colorings, t = (σ, σ ) ∈ F be some transition, and j ∈ [n] be an integer. Denote the flow routed through t from α to β in phase j by f j,t,α,β . Note that we are only considering the flow routed through t during phase j; it is possible that the hybrid path passes through t in several phases, possibly carrying a different flow each time. Intuitively, it seems natural that after the flow was split evenly several times, "not too much" flow is routed through any state,

as it has a specific combination of colors of the vertices of QS(j, t), and many such combinations are possible. It is not straightforward to show this, however, as the colors of different vertices in each state are not independent. The difficulty is compounded by the fact that flow is consolidated at the first step of every phase. Nevertheless, we can prove the following claim by rearranging the vertices of QS(j, t) and using an inductive reasoning on this new order.

Claim 3.4. The flow routed from α to β through any t = (σ, σ ) ∈ F in any phase j ∈ [n] is at most

f j,t,α,β ≤ π(α)π(β) ( ∆) |QS(j,t)| .
Proof. From Observation 3.3, (j, t) uniquely defines (j, ). If no flow is routed from α to β through t in phase j, the claim is trivially satisfied. Otherwise, we show that

f j, ,α,β ≤ π(α)π(β) ( ∆) |QS(j, )| ,
where f j, ,α,β is the maximal flow from α to β through any t at distance (j, ) from α. Order the vertices of QS(j, ) in reverse order of the time since their last color change (possibly a null color change). That is, the vertex whose color changed most recently is last in the order. Let M = |QS(j, )| and relabel the vertices of QS(j, ) by 1, . . . , M according to their place in this order. Similarly, relabel Φ α,β (j , ), by Φ 1 , . . . , Φ M , where Φ i is the set of states at the time just after vertex i last changed its color. In other words, Φ M = Φ α,β (j, + 1),Φ M -1 = Φ α,β (j, ), and so on. It is possible that for some m, Φ m corresponds to states in the previous phase, i.e., Φ m = Φ α,β (j -1, ). Note that we drop the α, β from the notation for clarity, but we are still only considering the flow from α to β. We now show by that for any set of m ≤ M colors c 1 , . . . , c m , at most π(α)π(β) ( ∆) m flow is routed into {σ ∈ Φ m : σ(i) = c i , i ∈ [m]}. In other words, fix the colors c 1 , . . . , c m . We want to bound the flow that passes through (into) the states of Φ m , where vertices 1, . . . , m are colored with c 1 , . . . , c m respectively. We do this by induction on m.

The base case:

The total flow from α to β through Φ i , for any i, is exactly π(α)π(β). For any c 1 ∈ [k], at most π(α)π(β) ∆ flow is routed through {σ ∈ Φ 1 : σ(1) = c 1 }. This is because the last time vertex 1 changed color, at most 1/ ∆ of all the flow was routed to states where v's color is c 1 .

The inductive step: From the inductive hypothesis, at most π(α)π(β)

( ∆) m-1 flow is routed through {σ ∈ Φ m-1 : σ(i) = c i , i ∈ [m -1]}.
From the construction of the hybrid paths, for each of these states, at most 1/ ∆ of the flow entering it flows to a state where vertex m is colored c m .

We want to bound the total flow through a transition in any single phase. The following set of recoloring functions χ is useful. Let C be a set of (available) colors. χ C is a function, parameterized by C, that takes as an input a color c ∈ [k]. Its output is a color from C, such that each color in C has the same number of pre-images, up to one. We do not explicitly define χ, only note that such a set of functions exists. For example, if k = 13, C = {1, 2, 3, 4, 5}, χ C could allocate (c mod 5) + 1 to every c ∈ [k], giving each color in C either two or three pre-images. We make the following observation (recall we assume ∆, (1 + )∆ and (1 + ) -1 are integers). Armed with Claim 3.4 and the functions χ, we are now ready to bound the total flow through a transition in any single phase.

Lemma 3.6. The flow f j,t routed through any t = (σ, σ ) ∈ F in any phase j ∈ [n] satisfies

f j,t ≤ π(•) 2 |C p | • (1 + ) -1 2|S j | ,
where π(•) is the probability of any state at stationarity. Proof. For each (j, t), where j ∈ [n] and t = (σ, σ ) ∈ F , denote by pairs j,t the set of pairs of states α, β ∈ C 2 p whose paths pass through t in phase j. We describe a function µ j,t whose domain is pairs j,t . We view the co-domain of µ j,t as the Cartesian product of 3 sets X, Y and Z: µ j,t : pairs j,t → X × Y × Z; the output of µ j,t (•) is a triple (x, y, z). The function will be injective, therefore the size of the co-domain of µ j,t will serve as an upper bound to |pairs j,t |.

The sets X, Y, Z are the following.

• X is the set of all proper colorings. Assume that the input to µ j,t is some pair (α, β). In the coloring specified by x, all vertices in A j 7 are colored by α. All vertices in B j are colored by β. Before specifying the coloring of S j under x, note that already, together with j and t, this allows us to deduce α completely on all vertices in V \ QS(j, t) and β on all vertices V \ S j . To determine the colors of S j in x, we color them one at a time, using χ. This information, while not characterizing β(v) completely for v ∈ S j , allows allows us to restrict the possible value of β(v) to a set of size at most (1 + ) -1 possible values.

• Y is (1 + ) -1 |S j | , allowing us to pinpoint β(v) for every v ∈ S j .
• Finally, Z is simply all possible colorings of the vertices of QS(j, t) under α.

Clearly x, y, z, j and t allow us to recover α and β. The size of the co-domain is at most

|C p | • (1 + ) -1 |S j | • k |QS(j,t)| .
Combining with Claim 3.4 we get that the total flow through any transition t at phase j is at most

f j,t ≤ |C p | • (1 + ) -1 |S j | • k |QS(j,t)| • π(•)π(•) ( ∆) |QS(j,t)| = π(•) 2 |C p | (1 + ) -1 |S j | • ((1 + )∆) |QS(j,t)| ( ∆) |QS(j,t)| ≤ π(•) 2 |C p | • (1 + ) -1 2|S j | ,
where the last inequality is because QS(j, t) ⊆ S j for any t.

7 As before, Aj = {v : v ≤ j}, except for = 0, for which Aj = {v : v < j}.

The congestion of an edge

We are ready to prove our main result of the section, that the congestion of any edge (σ, σ ) ∈ F under the flow defined by the hybrid paths from proper coloring to proper colorings, is polynomial in the number of vertices.

Lemma 3.7. The congestion of any transition t under f , when f is restricted to flows from proper colorings to proper colorings, satisfies

ρ f (t) ≤ 2k(λ + 1)n 3 log n (1 + ) -1 2 pw(G) .
Proof. From the definition of the congestion on an edge (Equation ( 6)), we have

ρ f (t) = 1 q(t) α,β∈Ω p:t∈p∈P(α,β) f (p)|p| ≤ (λ + 1)n log n q(t) α,β∈Ω p:t∈p∈P(α,β) f (p) (7a) = 2|Ω|k(λ + 1)n 2 log n α,β∈Ω p:t∈p∈P(α,β) f (p) (7b) = 2|Ω|k(λ + 1)n 2 log n n j=1 α,β∈Ω f j,t,α,β (7c)
= 2|Ω|k(λ + 1)n 2 log n n j=1 f j,t ≤ 2|Ω|k(λ + 1)n 2 log n n j=1 π(•) 2 |C p | • (1 + ) -1 2|S j | (7d) = 2|C p |k(λ + 1)n 2 log n |Ω| n j=1 (1 + ) -1 2|S j | ≤ 2k(λ + 1)n 3 log n (1 + ) -1 2 pw(G) .
Inequality (7a) is because the length of any hybrid path is at most (λ + 1)n log n; Equality (7b) is due to the definition of q: q(σ, σ ) = π(σ)P (σ, σ ), where π(σ) = |Ω| -1 and P (σ, σ ) = (2kn) -1 ; Equality (7c) is simply a rephrasing that holds because α,β∈Ω p:t∈p∈P(α,β)

f (p)
is the flow through t under f ; Inequality (7d) is due to Lemma 3.6. The final inequality is due to Theorem 2.6, as the pathwidth of a graph equals its vertex separation number.

Mixing time

Lemma 3.7 applies to the congestion from flow between proper colorings only. We extend this result to all of f . We rephrase our main lemma:

Lemma 3.1. The congestion of any transition t under f satisfies ρ f (t) ≤ 8k 3 (λ + 1)n 5 log n (1 + ) -1 2 pw(G) .

Proof. We use the function g from singly-flawed to proper colorings described in Corollary 2.3 to define the flows that have a singly-flawed coloring as (at least) one of their endpoints. For every α, β such that α ∈ C sf and β ∈ C p , we route the entire flow on the transition (α, g (α)) and then proceed using the canonical paths described above for routing the flow from g (α) to β. If α ∈ C p , and β ∈ C sf , we route the flow from α to g (β) using the canonical paths above and then on the edge (g (β), β). Finally, if α, β ∈ C sf , we route the entire flow on (α, g (α)), use the canonical paths above to route from g (α) to g (β) and finally route the entire flow on (g (β), β). For every state σ ∈ C p , there are at most kn states σ ∈ C sf : g (σ ) = σ. Therefore, we have multiplied the flow on every edge by at most

k 2 n 2 + 2kn + 1 < 4k 2 n 2 , (8)
where the first term is for pairs α, β ∈ C sf , the third is for α, β ∈ C p , and the second term on the left hand side is for mixed pairs. We added a further

knπ(•) 2 |Ω| = 2kn |Ω| < 1 (9)
to each edge (σ, g (σ)) and (g (σ), σ): there are at most |Ω| paths from a state σ ∈ C p (to any other state), hence at most kn|Ω| paths from any σ ∈ C sf . We absorb Inequality ( 9) and the fact that pw(G) + log n = (λ + 1) log n into Inequality [START_REF] Chekuri | A note on multiflows and treewidth[END_REF]. Multiplying the bound of Lemma 3.7 by 4k 2 n 2 gives the required bound.

The sampling algorithm

In order to sample a proper coloring, we need to execute the Markov chain sufficiently many times to guarantee that w.h.p. it outputs a proper coloring, and when it does, return that coloring. The pseudo code is given as Algorithm 1. For graphs of pathwidth bounded by O(log n), the algorithm runs time polynomial in n and log δ, where δ is the required bias parameter. Proof. We denote by π the distribution reached by MC after τ (δ 1 ) steps. By definition, the total variation distance between and π and π is at most δ 1 , hence for any S ⊂ Ω, it holds that |π(S) -π(S)| ≤ δ 1 .

(10)

Choosing S = C p and applying Corollary 2.2 gives that the probability of the final state being a proper coloring is at least 1 kn+1 -δ 1 . Our choice of T is so that Hoeffding's bound guarantees that Algorithm 1 will output a proper coloring during the for loop (i.e., a final state of the Markov chain and not an arbitrary coloring), with probability at least 1 -δ H , where δ H ≤ δ 3 . To show that Algorithm 1 is an almost uniform sampler for proper colorings, we need to show that the sampled coloring is drawn from a distribution that is close to uniform. In other words, if σ is the state output by Algorithm

Lemma 2 . 1 .

 21 For any G = (V, E) such that |V | = n and k ≥ ∆ + 2, there exists a surjective function g :

Observation 3 . 5 .

 35 For χ C as defined above, if k = (1 + )∆ and |C| ≥ ∆, each color in C has at most (1 + ) -1 pre-images in [k].

Algorithm 1 :

 1 An almost-uniform sampler for proper coloringsInput : G = (V, E) with maximal degree ∆, a number of colors k ≥ ∆ + 2, a bias parameter δ > 0 Output: a proper k-coloring of G Set = k ∆ ; Set δ 1 = δ/(kn + 1) 2 ; Set T = ln(3/δ)(kn + 2) 2 ; for t = 1 to T doSimulate MC(G, ) for τ (δ 1 ) steps, starting from an arbitrary proper coloring; If the final state σ is a proper coloring, return σ; Return an arbitrary proper coloring; Theorem 4.1. Algorithm 1 is a fully polynomial almost uniform sampler for proper colorings with bias parameter δ.

Table 1 :

 1 Comparison of results on sampling k-colorings.

	Degree	Girth	Graph family	k >	Dynamics	Mixing time Reference
	any	any	any	2∆	Glauber	O(n log n)	[26]
	any	any	any	(1.833 . . .)∆	Flip	O(n log n)

  1, then for any S ⊆ C p where (11a) is the probability that the Algorithm outputs a proper coloring and it is in S; (11b) is due to Equation (10); (11c) is because a-1 b+1 ≥ a+2 b for b ≥ a. The complementary Pr[σ ∈ S] ≤ π(S) π(Cp) + δ is immediate by considering the set C p \ S: if this were not the case then it would hold that Pr[σ ∈ S] + Pr[σ ∈ C p \ S] > 1.

	π(S) π(C p )	-δ ≤ Pr[σ ∈ S] ≤	π(S) π(C p )	+ δ.
	Pr[σ ∈ S] ≥	π(S) π(C p )	(1 -δ H )		(11a)
		≥	π(S) π(C p )	-δ H
		≥	π(S) -δ 1 π(C p ) + δ 1	-δ H	(11b)
		≥	π(S) -2δ 1 π(C p )	-δ H	(11c)
		=	π(S) π(C p )	-	2δ 1 π(C p )	-δ H
		≥	π(S) π(C p )	-	2δ 3	-	δ 3	,

We define precisely what we mean by "almost" in Section

2.2.2 Assuming (1 + )∆ ≥ ∆ + 1.

In the underlying graph of the transition matrix A of a Markov chain, the states are represented by vertices, there is an edge (u, v) between two states u, v ∈ Ω with weight we = Au,v if Au,v = 0.

Alternatively, we can define it as dT V (µ, ν) = 1 2 σ∈Ω |µ(σ) -ν(σ)|. It is easy to verify that the two definitions are equivalent.

Traditionally, a vertex separator for j is defined such that the separating subset appears before j in the ordering[START_REF] Ellis | The vertex separation and search number of a graph[END_REF]. This is identical to our definition with the order inverted.

For = 1, we consider (j -1, |Sj-1| + 2) instead of (j, 1), unless j = 1, in which case the vertices are all colored by α.

Acknowledgements We thank Leonard Schulman for valuable discussions, and Adam Wierman, Leonard Schulman and the anonymous reviewers for comments on earlier versions of this draft.