Department of Computer Science, University of California, Irvine, United
<EMAIL_ADDRESS>Department of Computer Science and Software
Engineering, California Polytechnic State University, San Luis Obispo, United
Statesdfrishbe@calpoly.eduhttps://orcid.org/0000-0002-1861-5439 David Eppstein
and Daniel Frishberg [100]Theory of computation Random walks and Markov chains

###### Acknowledgements.

The authors wish to acknowledge a number of helpful conversations on this
topic with Milena Mihail, Ioannis Panageas, Eric Vigoda, Charlie Carlson, and
Zongchen Chen, as well as with Karthik Gajulapalli, Hadi Khodabande, and Pedro
Matias.John Q. Open and Joan R. Access 2 42nd Conference on Very Important
Topics (CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016 Little Whinging,
United Kingdom 42 23

# Rapid mixing for the hardcore Glauber dynamics and other Markov chains in
bounded-treewidth graphs

David Eppstein  Daniel Frishberg

###### Abstract

We give a new rapid mixing result for a natural random walk on the independent
sets of a graph $G$. We show that when $G$ has bounded treewidth, this random
walk—known as the _Glauber dynamics_ for the _hardcore model_ —mixes rapidly
for all fixed values of the standard parameter $\lambda>0$, giving a simple
alternative to existing sampling algorithms for these structures. We also show
rapid mixing for analogous Markov chains on dominating sets, $b$-edge covers,
$b$-matchings, maximal independent sets, and maximal $b$-matchings. (For
$b$-matchings, maximal independent sets, and maximal $b$-matchings we also
require bounded degree.) Our results imply simpler alternatives to known
algorithms for the sampling and approximate counting problems in these graphs.
We prove our results by applying a divide-and-conquer framework we developed
in a previous paper, as an alternative to the _projection-restriction_
technique introduced by Jerrum, Son, Tetali, and Vigoda. We extend this prior
framework to handle chains for which the application of that framework is not
straightforward, strengthening existing results by Dyer, Goldberg, and Jerrum
and by Heinrich for the Glauber dynamics on $q$-colorings of graphs of bounded
treewidth and bounded degree.

###### keywords:

Glauber dynamics, mixing time, projection-restriction, multicommodity flow

###### category:

##  1 Introduction

The _Glauber dynamics_ on independent sets in a graph—motivated in part by
modeling systems in statistical physics—is a Markov chain in which one starts
at an arbitrary independent set, then repeatedly chooses a vertex at random
and, with probability that depends on a fixed parameter $\lambda>0$, either
removes the vertex from the set (if it is in the set), or adds it to the set
(if it is not in the set and has no neighbor in the set). This chain, which
samples from the _hardcore model_ on independent sets, has seen recent rapid
mixing results under various conditions. In addition to independent sets,
similar dynamics have been studied for a number of other structures—including,
for example, $q$-colorings, matchings, and edge covers (more generally,
$b$-matchings and $b$-edge covers).

###  1.1 Our contribution

We prove that the hardcore Glauber dynamics mixes rapidly on graphs of bounded
treewidth for all fixed $\lambda>0$, and that the Glauber dynamics on partial
$q$-colorings (for all $\lambda>0$) of a graph of bounded treewidth, and on
$q$-colorings of a graph of bounded treewidth and degree, mix rapidly. Marc
Heinrich proved the latter result, namely for $q$-colorings, in a 2020
preprint [28]. Heinrich’s result applies to all graphs of bounded treewidth;
however, for graphs of bounded treewidth and degree, whose degree is less than
quadratic in their treewidth, we improve on Heinrich’s upper bound—provided
that $q$ is fixed. We also prove that the analogous dynamics on the $b$-edge
covers (when $b$ is bounded) and the dominating sets of a graph of bounded
treewidth mix rapidly for all $\lambda>0$. In a similar vein, we prove that
three additional chains—on $b$-matchings (when $\lambda>0$), on maximal
independent sets, and on maximal $b$-matchings—mix rapidly in graphs of
bounded treewidth and degree.

To prove our results, we apply a framework we introduced in a companion paper
[18] that uses the _multicommodity flow_ technique (essentially the same as
the _canonical paths_ technique) for bounding mixing times. (We previously
presented this framework in a preprint of the present paper [17].) The
framework consists of a set of conditions (which we will define in Section
3.3) that guarantee rapid mixing; these conditions make progress towards
unifying prior work on similar Glauber dynamics with prior work on
probabilistic graphical models. In that paper [18], we also proved that the
_flip walk_ on the _$k$ -angulations_ of a convex $n$-point set mixes in time
quasipolynomial in $n$ for all fixed $k\geq 3$, although the special case
$k=3$ was known already to mix rapidly [38]. Thus our framework applies beyond
graphical models and graph sampling problems.

###  1.2 Main results

Our main results are the following (see Section 2 for relevant definitions).

######  Theorem 1.1.

The hardcore Glauber dynamics mixes in time $n^{O(t)}$ on graphs of treewidth
$t$ for all fixed $\lambda>0$.

######  Theorem 1.2.

The (unbiased) Glauber dynamics on $q$-colorings (when $q\geq\Delta+2$ is
fixed) mixes in time $n^{O(t)}$ on graphs of treewidth $t$ and bounded degree
when $q$ is fixed. The Glauber dynamics on partial $q$-colorings (when
$q\geq\Delta+2$ is fixed) mixes in time $n^{O(t)}$ on graphs of treewidth $t$
for all fixed $\lambda>0$.

######  Theorem 1.3.

The Glauber dynamics on $b$-edge covers mixes in time $n^{O(t^{2})}$ on graphs
of treewidth $t$, for all fixed $b\geq 1$ and fixed $\lambda>0$. The Glauber
dynamics on dominating sets mixes in time $n^{O(t)}$ on graphs of treewidth
$t$ for all fixed $\lambda>0$. The Glauber dynamics on $b$-matchings mixes in
time $n^{O(t)}$ on graphs of treewidth $t$ and bounded degree $\Delta$ for all
fixed $\lambda>0$ and fixed $b\geq 1$.

######  Theorem 1.4.

There exist Markov chains on maximal independent sets and maximal
$b$-matchings, whose stationary distributions are uniform, that mix in time
$n^{O(t)}$ on graphs of treewidth $t$ and bounded degree.

###  1.3 The framework: recursive flow construction

A _multicommodity flow_ in an undirected graph $G=(V,E)$ with $n$ vertices is
a set of $n^{2}$ flows, one flow for each ordered pair of vertices $(s,t)$,
where each flow sends one unit of a commodity from $s$ to $t$. More precisely,
take each (undirected) edge in $E$ and make two directed copies, one in each
direction; let $E^{+}=\bigcup_{\\{u,v\\}\in E}\\{(u,v),(v,u)\\}$ denote the
set of all these directed copies. A multicommodity flow is a collection of
functions $f_{st}:E^{+}\rightarrow\mathbb{R}_{\geq 0}$ such that each $f_{st}$
is a valid flow function, with $s$ (respectively $t$) having net out flow
(respectively in flow) equal to one, and all other vertices having zero net
flow. If a multicommodity flow exists in $G$ with small _congestion_ —i.e. one
in which no edge carries too much flow—then the natural Markov chain whose
states are the vertices of $G$ mixes rapidly.

The chains we analyze are natural random walks on a _Glauber graph_
$\mathcal{M}_{\textnormal{}}(G)$111The chains on maximal independent sets and
maximal $b$-matchings are not strictly Glauber dynamics, but we will use the
same term for the graph, redefining the edge set as pairs connected by the
moves we define in Appendix C.1.—the graph whose vertices are the structures
over which the random walk is performed, and whose edges are the pairs of
these structures with symmetric distance equal to one. For example, in the
case of independent sets, $\mathcal{M}_{\textnormal{}}(G)$ has as its vertex
set the collection of all independent sets in $G$, and as its edge set the
collection of all (unordered) pairs of independent sets $S,S^{\prime}$ in $G$
such that $S=S^{\prime}\cup\\{v\\}$ for some $v\in V(G)$. Thus each of these
random walks is performed on a graph that may be exponentially large with
respect to the size of the input graph. In our previous work [18], we showed
that when all of a certain set of conditions hold, we can construct a
multicommodity flow in $\mathcal{M}_{\textnormal{}}(G)$ with congestion
polynomial in $n=|V(G)|$, implying that the walk on
$\mathcal{M}_{\textnormal{}}(G)$ mixes rapidly. The conditions specify that
$\mathcal{M}_{\textnormal{}}(G)$ can be partitioned into a small number of
induced subgraphs, all of which are approximately the same size, with large
numbers of edges between pairs of the subgraphs. The conditions require that
each of these induced subgraphs can be decomposed into smaller Glauber graphs
that are similar in structure to $\mathcal{M}_{\textnormal{}}(G)$. This self
similarity allows for the recursive construction of a multicommodity flow, by
assembling flows on smaller Glauber graphs together into a flow in
$\mathcal{M}_{\textnormal{}}(G)$ with small congestion.

###  1.4 Projection-restriction and prior work on the hardcore model

Prior work on rapid mixing of Markov chains on subset systems includes the
special case of matroid polytopes. For this case, recent results [3, 2] have
partly solved a 30-year-old conjecture of Mihail and Vazirani [39]. Other
prior work uses multicommodity flows (and the essentially equivalent
_canonical paths_ technique) to obtain polynomial mixing upper bounds on
structures of exponential size, including matchings and 0/1 knapsack solutions
[40, 25]. Madras and Randall [36] used a decomposition of the hardcore model
state space to prove rapid mixing under different conditions. We also
decompose the state space, but our approach is different and is more similar
to Heinrich’s [28] application of the _projection-restriction_ technique
introduced by Jerrum, Son, Tetali, and Vigoda [30]. This technique involves
partitioning the state space of a chain into a collection of sub-state spaces,
each of which internally has a good _spectral gap_ —a property that implies
rapid mixing—and all of which are well connected to one another. Heinrich used
the vertex separation properties of bounded-treewidth graphs to obtain an
inductive argument: the resulting sub-spaces are themselves _Cartesian
products_ of chains on smaller graphs, and thus mix rapidly. (See Lemma 3.10.)
We partition the state space recursively using the same vertex separation
properties, and indeed for the chains on $b$-matchings and $q$-colorings in
bounded-treewidth, bounded-degree graphs, combining these properties
straightforwardly with the existing spectral projection-restriction machinery
of [30] suffices for rapid mixing. The main contribution in this paper is to
extend the framework to chains for which this application is not
straightforward. That is, we give general conditions for constructing a
multicommodity flow in the projection chain with small congestion, giving a
good spectral gap in the projection chain. One may then apply induction using
the spectral machinery of [30] to obtain rapid mixing in the overall chain;
alternatively, one can substitute the flow-based machinery from our companion
paper [18] for the spectral technique.

In the case of independent sets, Jerrum, Son, Tetali, and Vigoda [30] applied
their technique to a special case of the hardcore model, namely regular trees.
However, it was not clear how to generalize this application to bounded-
treewidth graphs—since showing the spectral gap of the projection chain is
sufficiently large is not straightforward. Martinelli, Sinclair, and Weitz
[37] showed that the Glauber dynamics on the hardcore model mixes in $O(n\log
n)$ time on the complete $\Delta-1$-ary tree with $n$ nodes, but they did not
address general trees. Berger, Kenyon, Mossel, and Peres [4] showed rapid
mixing for $q$-colorings of regular trees with unbounded degree but also did
not address general trees. Our first main technical contribution is to show
rapid mixing for general bounded-treewidth graphs by introducing the
_hierarchical_ version of our framework, in which we construct a flow with
small congestion in the projection chain; we show that this construction gives
rapid mixing for dominating sets, _partial_ $q$-colorings, and $b$-edge covers
in bounded-treewidth graphs. We solve another problem: the technical theorem
in [30] as stated requires each of the state spaces in the partition to be a
Cartesian product of chains on smaller spaces. For four of our eight
chains—those on dominating sets, $b$-edge covers, maximal $b$-matchings, and
maximal independent sets—the sub-spaces obtained in the decomposition are not
a disjoint union of Cartesian products but may each be a union of Cartesian
products, or may be mutually intersecting. In some cases, the sub-spaces may
even induce disconnected restriction chains. Our second main contribution is
to resolve this problem, using the structure of the state spaces of Glauber
dynamics as graphs. We discuss this in Appendix A.4.

###  1.5 Paper organization

In Section 2, we give relevant background. In Section 3.3, we use the chain on
independent sets to review the “non-hierarchical” version of our framework
(the version we gave in our companion paper)—which works for this chain when
treewidth and degree are bounded. In Sections E.1 and E.2 we apply it to
$q$-colorings and to $b$-edge covers and $b$-matchings. To fully prove Theorem
1.1 and Theorem 1.3, we need to deal with unbounded-degree graphs—our first
main technical contribution. In Section 4, we modify the framework to do so,
proving Theorem 1.1 for $\lambda=1$. We defer some details to Appendix F,
where we also finish the proof of Theorem 1.2 for $\lambda=1$. We prove the
general case $\lambda>0$ of Theorems 1.1 and 1.2 in Appendix G. We finish the
proofs of Theorems 1.3 and 1.4 in Appendix H: applying the framework to the
relevant chains requires a further refinement of the framework. In all of the
above, we prove rapid mixing but defer derivation of specific upper bounds to
Section D.

##  2 Preliminaries

###  2.1 Glauber dynamics

######  Definition 2.1.

The _hardcore Glauber dynamics_ on a graph $G$ is the following chain, defined
with respect to a fixed real parameter $\lambda>0$:

  1. 1.

Let $X_{0}$ be an arbitrary independent set in $G$.

  2. 2.

For $t\geq 0$, select a vertex $v\in V(G)$ uniformly at random.

  3. 3.

If $v\notin X_{t}$ and $X_{t}\cup\\{v\\}$ is not a valid independent set, do
nothing.

  4. 4.

Otherwise:

Let $X_{t+1}=X_{t}\cup\\{v\\}$ with probability $\lambda/(\lambda+1)$.

Let $X_{t+1}=X_{t}\setminus\\{v\\}$ with probability $1/(\lambda+1)$.

Graph-theoretically, the Glauber dynamics is defined as follows: let the
_indepdendent set Glauber graph_ $\mathcal{M}_{\textnormal{IS}}(G)$ denote the
graph whose vertices are identified with the independent sets of a given graph
$G$, and whose edges are the pairs of independent sets whose symmetric
difference is one. The hardcore Glauber dynamics is a Markov chain,
parameterized by $\lambda>0$, with state space
$\Omega=V(\mathcal{M}_{\textnormal{IS}}(G))$ and probability matrix $P$, where
for $S,S^{\prime}\in V(\mathcal{M}_{\textnormal{}}(G))$ with $S\neq
S^{\prime}$, $P(S,S^{\prime})=\lambda/(\Delta_{\mathcal{M}}(\lambda+1))$ when
$|S^{\prime}\setminus S|=1$, and
$P(S,S^{\prime})=1/(\Delta_{\mathcal{M}}(\lambda+1))$ when $|S\setminus
S^{\prime}|=1$. If $S=S^{\prime}$, then
$P(S,S^{\prime})=1-\sum_{S^{\prime\prime}\neq S}P(S,S^{\prime\prime})$. (Here
$\Delta_{\mathcal{M}}$ is the maximum degree of the Glauber graph—i.e. the
maximum number of neighboring states that a state $S$ can have.) The Glauber
graph has vertex set $\Omega$ and adjacency matrix $P$—up to the addition of
self loops and normalization by degree. (When $\lambda\neq 1$ this graph can
still be augmented with suitable weights so that the walk on the graph is the
Glauber dynamics.)

###  2.2 Mixing time

To generate, approximately uniformly at random, an object of a given
class—such as an independent set in a given graph—one can conduct a random
walk on a graph whose vertices are the objects of interest, and whose edges
represent local moves between the objects (or states). It is known that under
certain mild conditions satisfied by as all our chains (see Appendix G.1), the
walk converges to the uniform distribution in the limit. The rate of
convergence is important: in the case of subset systems such as those we
consider, the walk takes place over an exponentially large number of subsets
defined over an underlying set of size $n$. If the convergence, or _mixing
time_ , of the walk is polynomial in $n$, then the random walk is said to be
_rapidly mixing_. The mixing time is denoted $\tau(\varepsilon)$, where
$\varepsilon$ denotes the desired precision of convergence to the uniform
distribution, and the value of $\tau$ at $\varepsilon$ is the minimum number
of steps in the random walk before convergence is guaranteed. Convergence is
measured via the _total variation distance_ [48] between the distribution over
states induced by the walk at a given time step, and the uniform distribution.
One can obtain non-uniform _stationary_ distributions by weighting the
graph—see Appendix G.1. See Levin, Peres, and Wilmer [34] for a comprehensive
treatment of rapid mixing.

A Markov chain, given a starting state $S\in\Omega$, induces a probability
distribution $\pi_{t}$ at each time step $t$. The Glauber dynamics is known,
regardless of starting state, to converge in the limit to a _stationary_
distribution $\pi^{*}(S)=\lambda^{|S|}/Z(\mathcal{M}_{\textnormal{}}(G)),$
where the term $Z(\mathcal{M}_{\textnormal{}}(G))$ is simply a normalizing
value. When $\lambda$ is unspecified, assume $\lambda=1$ (the uniform case).
The _mixing time_ is defined as follows:

Given an arbitrary $\varepsilon>0$, the _mixing time_ , $\tau(\varepsilon)$,
of a Markov chain with state space $\Omega$ and stationary distribution
$\pi^{*}$ is the minimum time $t$ such that, regardless of starting state, we
always have $\frac{1}{2}\sum_{S\in\Omega}|\pi(S)-\pi^{*}(S)|<\varepsilon.$
Suppose the chain belongs to a family of Markov chains, the size of whose
state space is parameterized by some value $n$. Here, $|\Omega|$ may be
exponential in $n$. If $\tau(\varepsilon)$ is bounded by a polynomial function
in $\log(1/\varepsilon)$ and in $n$, the chain is said to be _rapidly mixing_.
It is common to omit the parameter $\varepsilon$ and assume $\varepsilon=1/4$.

###  2.3 Treewidth and vertex separators

######  Definition 2.2.

[45] A _tree decomposition_ of a graph $G=(V,E)$ is a collection of sets
$\\{X_{i}\\},i=1,\dots,k$, called _bags_ , together with a tree $T$, whose
nodes are identified with the bags $\\{X_{i}\\}$, such that all of the
following hold:

  1. 1.

Every vertex in $V$ lies in some bag, i.e. $\bigcup_{i=1}^{k}X_{i}=V$.

  2. 2.

For every $(u,v)\in E$, the vertices $u$ and $v$ belong to at least one bag
$X_{i}$ together, i.e. for some $i$, $u\in X_{i}$ and $v\in X_{i}$.

  3. 3.

The collection of all bags containing any given vertex $v\in V$, i.e.
$\\{X_{i}\mid v\in X_{i}\\}$ forms a (connected) subtree of $T$.

######  Definition 2.3.

[45] The _width_ of a tree decomposition is one less than the size of the
largest bag in the decomposition. The _treewidth_ of a graph $G$ is the
minimum $t$ such that a tree decomposition of $G$ exists with width $t$.

Intuitively, treewidth measures how far away a graph is from being a tree. For
example, trees have treewidth one; a graph consisting of a single cycle of
size at least three has treewidth two. Treewidth is of interest in large part
because many NP-hard problems become tractable on graphs of bounded treewidth.
For a full definition of treewidth and a survey of this phenomenon, known as
_fixed-parameter tractability_ , see [7].

For our purposes, treewidth is of interest due to its relationship to _vertex
separators_ : a vertex set $X\subseteq V$ in a graph $G=(V,E)$ is called a
_vertex separator_ if the deletion of $X$ from $V$ leaves the induced subgraph
on the remaining vertices disconnected. Say that $X$ is a _balanced separator_
if deleting $X$ partitions $V$ into mutually disconnected subsets $A\cup
B=V\setminus X$ such that $|V|/3\leq|A|\leq|B|\leq 2|V|/3$. A graph $G$ is
_recursively $s$-separable_ [19] if either (i) $|V(G)|\leq 1$, or (ii) $G$ has
a balanced separator $X$ with $|X|\leq s$ and, after deleting $X$, the
resulting subsets $A$ and $B$ induce subgraphs of $G$ that are each
recursively $s$-separable.

The following is known and easy to prove [19]:

######  Lemma 2.4.

Every graph with treewidth $t\geq 1$ is recursively $s$-separable for all
$s\geq t+1$.

##  3 $\lambda=1$: Bounded treewidth and degree

To build up to the proof of Theorem 1.1, we first show a weaker result: that
the unifrom hardcore Glauber dynamics mixes rapidly in graphs of bounded
treewidth and degree. Fully proving Theorem 1.1, even in the unbiased case,
requires the non-hierarchical framework. The main technical lemma in this
section, Lemma 3.11, comes from our companion paper. Our contribution in this
paper is the application to independent sets in graphs of bounded treewidth
and degree—which we strengthen to graphs of bounded treewidth in Section 4.

The following is necessary for the Glauber dynamics to sample correctly:

######  Lemma 3.1.

The independent set Glauber graph is connected.

######  Proof 3.2.

Consider the empty independent set $\emptyset$. Every independent set $S\in
V(\mathcal{M}_{\textnormal{IS}}(G))$ has a path of length $|S|$ to
$\emptyset$, formed by removing each vertex in $S$ in arbitrary order.

###  3.1 Partitioning the vertices of $\mathcal{M}_{\textnormal{IS}}(G)$ into
classes

The vertices of the Glauber graph $\mathcal{M}_{\textnormal{IS}}(G)$ are
subsets of the vertices of an underlying graph $G$. When $G$ has bounded
treewidth, we can choose a small separator $X$ that partitions $V(G)\setminus
X$ into two mutually disconnected vertex subsets, $A$ and $B$, each of which
has at most $2|V(G)|/3$ vertices. Consider the problem of sampling an
independent set $S$ from $G$. Given a separator $X$ for $G$, partition the
independent sets in $G$ into equivalence classes as follows:

######  Definition 3.3.

Let $G=(V,E)$ be a graph. Let $\mathcal{M}_{\textnormal{IS}}(G)$ be the
independent set Glauber graph we have defined. Let $X\subseteq V$ be a vertex
separator for $G$. Let $\mathcal{S}_{\textnormal{IS}}(G)$ be the set of
equivalence classes of $V(\mathcal{M}_{\textnormal{IS}}(G))$ in which two
independent sets $S$ and $S^{\prime}$ are in the same class if $S\cap
X=S^{\prime}\cap X$. Let $T=S\cap X$, and call the corresponding class
$\mathcal{C}_{\textnormal{IS}}(T)$.

(Technically $X$ is also a parameter for $\mathcal{S}_{\textnormal{IS}}(G)$
and $\mathcal{C}_{\textnormal{IS}}(T)$, but we omit it for ease of notation.)

See Figure 1 for an example of a partitioning.

Figure 1: Two independent sets in a graph $G$: $S$ (left) and $S^{\prime}$
(right), belonging to distinct classes. $S$ and $S^{\prime}$ differ by a move,
with the separator $X$ inducing the classes to which the sets belong.
$S^{\prime}$ results from adding $v$ to $S$. $|S^{\prime}|<|S|$, since
$S^{\prime}$ excludes those independent sets that contain $u$.

The _Cartesian product_ of two graphs $H$ and $J$ is the graph whose vertex
set is $V(H)\times V(J)$ and whose edges are the pairs
$((h_{1},j_{1}),(h_{2},j_{2}))$ such that either $h_{1}=h_{2}$ and
$(j_{1},j_{2})\in E(J)$ or else $(h_{1},h_{2})\in E(H)$ and $j_{1}=j_{2}$.

Let $A$ and $B$ be the mutually disconnected vertex subsets into which the
removal of $X$ partitions $V(G)\setminus X$. Given a fixed independent subset
$T\subseteq X$, identify the independent sets in
$\mathcal{C}_{\textnormal{IS}}(T)$ with the pairs of the form $(S_{A},S_{B})$,
where $S_{A}$ is an independent set in $A\setminus N_{A}(T)$, and $S_{B}$ is
an independent set in $B\setminus N_{B}(T)$, where $N_{A}(T)$ and $N_{B}(T)$
denote the union of the neighborhoods of vertices in $T$, in $A$ and $B$
respectively. That is, identify each independent set in
$\mathcal{C}_{\textnormal{IS}}(T)$ with a pair of an independent set in $A$
that avoids neighbors of vertices in $T$, and a similar independent set in
$B$. Consider the two Glauber graphs $\mathcal{M}_{\textnormal{IS}}(A\setminus
N_{A}(T))$ and $\mathcal{M}_{\textnormal{IS}}(B\setminus N_{B}(T))$, whose
vertices are respectively the independent sets in $G[A\setminus N_{A}(T)]$,
and those in $G[B\setminus N_{B}(T)]$. If two independent sets
$S=(S_{A},S_{B})$ and $S^{\prime}=(S_{A}^{\prime},S_{B}^{\prime})$ belong to
the same class, then a _move_ (traversal of an edge in the Glauber graph)
exists between $S$ and $S^{\prime}$ in $\mathcal{M}_{\textnormal{IS}}(G)$
precisely when a move exists between the restrictions of $S$ and $S^{\prime}$
to either $\mathcal{M}_{\textnormal{IS}}(A\setminus N_{A}(T))$ or
$\mathcal{M}_{\textnormal{IS}}(B\setminus N_{B}(T))$ (but not both).
Therefore, each class induces, in $\mathcal{M}_{\textnormal{IS}}(G)$, a
subgraph that is isomorphic to a Cartesian product of two smaller Glauber
graphs:

######  Lemma 3.4.

Given a graph $G$ and a vertex separator $X$ that partitions $V(G)$ into
subgraphs $A$ and $B$, for every class $T\in\mathcal{S}_{\textnormal{IS}}(G)$,
$\mathcal{C}_{\textnormal{IS}}(T)\cong\mathcal{M}_{\textnormal{IS}}(A\setminus
N_{A}(T))\Box\mathcal{M}_{\textnormal{IS}}(B\setminus N_{B}(T)).$

(Here by the symbol $\cong$ we denote isomorphism, and we identify the class
$\mathcal{C}_{\textnormal{IS}}(T)$ with the subgraph it induces in
$\mathcal{M}_{\textnormal{IS}}(G)$.)

###  3.2 Rapid mixing for the hardcore Glauber dynamics when $G$ has bounded
treewidth and degree

Figure 2: A schematic view of three classes in the independent set Glauber
graph $\mathcal{M}_{\textnormal{IS}}(G)$. The large circles denote classes
under the partition described in Section 3.1. The curved arrows illustrate the
construction of a flow in $\mathcal{M}_{\textnormal{IS}}(G)$ from an
independent set $S\in\mathcal{C}_{\textnormal{IS}}(T)$ to another independent
set $S^{\prime\prime}\in\mathcal{C}_{\textnormal{IS}}(T)$—and also to an
independent set $S^{\prime}\in\mathcal{C}_{\textnormal{IS}}(T^{\prime})$.
Here, $\mathcal{C}_{\textnormal{IS}}(T)$ and
$\mathcal{C}_{\textnormal{IS}}(T^{\prime\prime})$ are adjacent classes in
$\mathcal{M}_{\textnormal{IS}}(G)$, connected by a large number of edges, and
similarly $\mathcal{C}_{\textnormal{IS}}(T^{\prime})$ and
$\mathcal{C}_{\textnormal{IS}}(T^{\prime\prime})$ are adjacent. In Section 3.2
we formalize this flow.

As described in Section 3.1, we use a small vertex separator $X$ in $G$ to
give a decomposition of $\mathcal{M}_{\textnormal{IS}}(G)$ into subgraphs,
each of which has a Cartesian product structure—in which both factor graphs in
the product are themselves Glauber graphs. Since Cartesian products preserve
flow congestion upper bounds (see Lemma 3.10), this decomposition provides a
crucial inductive structure. We analyze this structure in this section.

######  Lemma 3.5.

Let $G$ be a graph with bounded treewidth $t$ and bounded degree $\Delta$, let
$\mathcal{M}_{\textnormal{IS}}(G)$ be as we have defined, and let
$\mathcal{S}_{\textnormal{IS}}(G)$ be as in Definition 3.3 with respect to a
small balanced separator $X$ with $|X|\leq t+1$. Then:

  1. 1.

The number of classes in $\mathcal{S}_{\textnormal{IS}}(G)$ is $O(1)$.

  2. 2.

For every pair of classes
$\mathcal{C}_{\textnormal{IS}}(T),\mathcal{C}_{\textnormal{IS}}(T^{\prime})\in\mathcal{S}_{\textnormal{IS}}(G)$,
$|\mathcal{C}_{\textnormal{IS}}(T)|=\Theta(1)|\mathcal{C}_{\textnormal{IS}}(T^{\prime})|$.

  3. 3.

Let
$\mathcal{C}_{\textnormal{IS}}(T),\mathcal{C}_{\textnormal{IS}}(T^{\prime})\in\mathcal{S}_{\textnormal{IS}}(G)$
be two classes. No independent set $S\in\mathcal{C}_{\textnormal{IS}}(T)$ has
more than one move to an independent set
$S^{\prime}\in\mathcal{C}_{\textnormal{IS}}(T^{\prime})$.

  4. 4.

Let
$\mathcal{C}_{\textnormal{IS}}(T),\mathcal{C}_{\textnormal{IS}}(T^{\prime})\in\mathcal{S}_{\textnormal{IS}}(G)$
be two classes. Suppose there exists at least one move between an independent
set in $\mathcal{C}_{\textnormal{IS}}(T)$ and an independent set in
$\mathcal{C}_{\textnormal{IS}}(T^{\prime})$. Then there exist at least
$\Omega(1)|\mathcal{C}_{\textnormal{IS}}(T)|$ moves between independent sets
in $\mathcal{C}_{\textnormal{IS}}(T)$ and independent sets in
$\mathcal{C}_{\textnormal{IS}}(T^{\prime})$.

######  Proof 3.6.

Claim 1 follows from the fact that $|\mathcal{S}_{\textnormal{IS}}(G)|\leq
2^{|X|}\leq 2^{t+1}=O(1),$ where the first inequality is true because each
class is identified with a subset of the vertices in $X$. The proofs of claims
2 through 4 are in Appendix I.

We will use Lemma 3.5 to prove the following, applying the framework from our
previous paper, in Section 3.3:

######  Lemma 3.7.

Given a graph $G$ with bounded treewidth and degree, the natural random walk
on the independent set Glauber graph $\mathcal{M}_{\textnormal{IS}}(G)$ has
mixing time $\tau(\varepsilon)=O(n^{c}\log{1/\varepsilon})$, where $c=O(1)$.

To prove Theorem 1.1, however, we need to get rid of the assumption that
degree is bounded. We address this issue in Section 4.

###  3.3 Abstraction into framework conditions

The observations in Lemma 3.5 correspond to a set of conditions we gave in our
previous work [18]. These conditions are, given a connected graph
$\mathcal{M}_{\textnormal{}}(G)$, on some set of combinatorial structures over
an underlying graph $G$ with $n$ vertices:

  1. 1.

The vertices of $\mathcal{M}_{\textnormal{}}(G)$ can be partitioned into a set
$\mathcal{S}$ of classes, where $|\mathcal{S}|=O(1).$

  2. 2.

The ratio of the sizes of any two classes in $\mathcal{S}$ is $\Theta(1)$.

  3. 3.

Given two classes
$\mathcal{C}_{\textnormal{}}(T),\mathcal{C}_{\textnormal{}}(T^{\prime})\in\mathcal{S}$,
no vertex in $\mathcal{C}_{\textnormal{}}(T)$ has more than $O(1)$ edges to
vertices in $\mathcal{C}_{\textnormal{}}(T^{\prime})$.

  4. 4.

For every pair of classes that share at least one edge, the number of edges
between the two classes is $\Theta(1)$ times the size of each of the two
classes.

  5. 5.

Each class in $\mathcal{S}$ is the Cartesian product of two graphs
$\mathcal{M}_{\textnormal{}}(G_{1})$ and $\mathcal{M}_{\textnormal{}}(G_{2})$,
each of which can be recursively partitioned in the same way as
$\mathcal{M}_{\textnormal{}}(G)$.

  6. 6.

The recursive partitioning mentioned in Condition 5 reaches the base case
(graphs with one or zero vertices) in $O(\log n)$ steps.

Conditions 1 through 4 correspond respectively to Lemma 3.5; Condition 5
corresponds to Lemma 3.4. Condition 6 corresponds to the observation at the
end of the proof sketch of Lemma 3.7.

We introduce some facts that we previously used to prove that these conditions
suffice for rapid mixing, via _expansion_ , then review a sketch of the proof;
we will build on these techniques in Section 4 (our main contribution) and in
the appendices.

The _edge expansion_ (or simply the _expansion_) of a graph $G=(V,E)$ is the
quantity $h(G):=\min_{S\subseteq V:|S|\leq|V|/2}\frac{|\\{(u,v)\in E\mid u\in
S,v\notin S\\}|}{|S|},$ i.e. the minimum quotient of the number of edges in
the cut by the number of vertices on the smaller side of the cut. The _vertex
expansion_ is the quantity $h(G):=\min_{S\subseteq
V:|S|\leq|V|/2}\frac{|\\{v\in V\setminus S\mid\exists u\in S,(u,v)\in
E\\}|}{|S|},$ i.e. the minimum quotient of the number of neighbors of a set
$S$ with $|S|\leq|V|/2$ that are not in $S$.

Mixing can be bounded from above via a lower bound on expansion [48] when the
degree of a Glauber graph is small (linear in the case of our chains):

######  Lemma 3.8.

Given a graph $\mathcal{M}=(\mathcal{V},\mathcal{E})$, consider the Markov
chain whose state space is $\mathcal{V}$ and whose transitions are of the form
$P(x,x)=1/2,P(x,y)=0\forall(x,y)\notin\mathcal{E},P(x,y)=1/(2\Delta)\forall(x,y)\in\mathcal{E}$,
where $\Delta$ is the maximum degree of $\mathcal{M}$. The mixing time of this
Markov chain is at most

$\tau(\varepsilon)=O\left(\frac{\Delta^{2}}{(h(\mathcal{M}))^{2}}\cdot\ln{\frac{|\mathcal{V}|}{\varepsilon}}\right).$

Expansion, in turn, can be bounded from below via an upper bound on the
_congestion_ of a multicommodity flow. Given a multicommodity flow
$f=\\{f_{st}|s,t\in V\times V\\}$ in a graph $G=(V,E)$, define the congestion
of $f$ as the quantity $\rho=\max_{(u,v)\in E^{+}}\sum_{s,t\in V\times
V}f_{st}(u,v),$ i.e. the maximum amount of flow sent across an edge.

######  Lemma 3.9.

[48]: For every graph $G=(V,E)$ and for every flow function $f$ defined over
$G$ and having congestion $\rho$, $h(G)\geq 1/(2\rho)$.

######  Lemma 3.10.

Given graphs $H$ and $J$, let $G$ be the Cartesian product $H\Box J$. Suppose
multicommodity flows exist in $H$ and $J$ with congestion at most $\rho_{H}$
and $\rho_{J}$ respectively. Then there exists a multicommodity flow in $G$
with congestion at most $\max\\{\rho_{H},\rho_{J}\\}$.

We proved Lemma 3.10 in [18], although an analogous result for expansion is
known [24]. We also proved the following in [18]. We review the lemma and give
a modified proof sketch here, in terms more intuitive for the chains we are
analyzing in this paper. We will modify the technique in Section 4.

######  Lemma 3.11.

Given a graph $\mathcal{M}_{\textnormal{}}(G)$ satisfying the conditions in
Section 3.3, the expansion of $\mathcal{M}_{\textnormal{}}(G)$ is
$\Omega(1/n^{c})$, where $c=O(1).$

######  Proof 3.12.

Partition $\mathcal{M}_{\textnormal{}}(G)$ into classes as in Definition 3.3.
By Lemma 3.4, each class
$\mathcal{C}_{\textnormal{}}(T)\in\mathcal{S}_{\textnormal{}}(G)$ is
isomorphic to the Cartesian product $\mathcal{M}_{\textnormal{}}(A\setminus
N_{A}(T))\Box\mathcal{M}_{\textnormal{}}(B\setminus N_{B}(T))$. We make an
inductive argument, in which the inductive hypothesis assumes that for each
such Cartesian product, the graphs $\mathcal{M}_{\textnormal{}}(A\setminus
N_{A}(T))$ and $\mathcal{M}_{\textnormal{}}(B\setminus N_{B}(T))$ have
multicommodity flows $f_{A}$ and $f_{B}$ with congestion $\rho_{A}\leq
c^{\log|V(G)|-1},\rho_{B}\leq c^{\log|V(G)|-1}$ respectively, for some
constant $c$. By Lemma 3.10, $\mathcal{C}_{\textnormal{}}(T)$ then has a flow
$f_{T}$ with congestion $\rho_{T}\leq c^{\log|V(G)|-1}.$ The inductive step is
to combine the $f_{T}$ flows for all of the classes, giving a flow $f$ in
$\mathcal{M}_{\textnormal{}}(G)$ with small congestion. We need to route flow
between every $S,S^{\prime}\in V(\mathcal{M}_{\textnormal{}}(G))$. If $S$ and
$S^{\prime}$ belong to the same class $\mathcal{C}_{\textnormal{}}(T)$, simply
use the same flow that $S$ uses to send its unit to $S^{\prime}$ in $f_{T}$.
If $S\in\mathcal{C}_{\textnormal{}}(T)$ and
$S^{\prime}\in\mathcal{C}_{\textnormal{}}(T^{\prime})\neq\mathcal{C}_{\textnormal{}}(T)$
belong to different classes, we find a sequence of intermediate classes
through which to route flow from $\mathcal{C}_{\textnormal{}}(T)$ to
$\mathcal{C}_{\textnormal{}}(T^{\prime})$. See Figure 2. We specified in our
companion paper [18] how to route the flow through each intermediate class so
that the congestion across each edges between a pair of classes is at most
$O(1)$, then made use of the existing flows within each class guaranteed by
the inductive hypothesis to bound the resulting amount of flow within each
class $\mathcal{C}_{\textnormal{}}(T)$. We showed that the latter is at most
$O(1)\cdot\rho_{T}$, giving overall congestion $O(1)^{l}$, where $l$ is the
number of induction levels. Since $X$ is a balanced separator we have
$l=O(\log n)$; the lemma now follows from Lemma 3.8.

The full proof of Lemma 3.11 is in our companion paper [18]. We will use the
phrase “non-hierarchical framework” to describe this set of conditions—which
apply to the chains we study when the underlying graph $G$ has bounded
treewidth and degree. Although Jerrum, Son, Tetali, and Vigoda [30] did not
consider bounded-treewidth graphs generally, these conditions do allow their
projection-restriction technique to be applied. In effect, Lemma 3.11 and its
proof, which we gave in our previous work, characterize a sufficient set of
conditions for applying Jerrum, Son, Tetali, and Vigoda’s technique:
specifically, one can, instead of routing flow internally through each
intermediate class, simply treat the construction above as a flow in the
projection graph, concluding that the projection graph has a good spectral
gap—then apply [30]. The first main technical contribution of this paper is in
Section 4, in which we give an alternative set of conditions—which we will
call our “hierarchical framework”—that allows us to handle underlying graphs
of unbounded degree (though treewidth still must be bounded), and to handle
chains other than the hardcore model. This will allow us to complete the
proofs of Theorems 1.1, 1.2, and 1.3.

##  4 $\lambda=1$: Unbounded degree

###  4.1 Hierarchical framework

We now sketch “hierarchical” framework conditions that guarantee rapid mixing
in the case of unbounded degree (when treewidth is bounded). Several of the
chains we consider satisfy these conditions so long as the treewidth of the
underlying graph is bounded. This is the first main technical contribution in
this paper. In the original framework, we assumed that the classes were
approximately the same size. Although all of the graphs to which we apply this
hierarchical framework satisfy this condition in graphs with bounded treewidth
and degree, this is not the case when the degree is unbounded. Fortunately, in
the case of independent sets, partial $q$-colorings, dominating sets, and
$b$-edge covers, we solve this problem with some modifications to the
framework.

###  4.2 Independent sets

Figure 3: Left: a schematic representation of the classes in the independent
set Glauber graph and edges between them when the degree is unbounded. Right:
a class $\mathcal{C}_{\textnormal{IS}}(T)$, with two parents,
$\mathcal{C}_{\textnormal{IS}}(P)$ and
$\mathcal{C}_{\textnormal{IS}}(P^{\prime})$, and two children,
$\mathcal{C}_{\textnormal{IS}}(C)$ and
$\mathcal{C}_{\textnormal{IS}}(C^{\prime})$. (Classes with larger cardinality
are drawn larger.) The parallel edges depict the fact that a child class
always has every one of its vertices adjacent to a vertex in a given parent
class, and that the edges between any given pair of classes are vertex-
disjoint.

In the proof of Lemma 3.11, the assumption that the classes were approximately
the same size allowed every class $\mathcal{C}_{\textnormal{IS}}(T)$ to route
flow for all pairs of vertices without being too congested, because
$\mathcal{C}_{\textnormal{IS}}(T)$ is sufficiently large. Once we discard this
assumption, we need to specify explicitly the path through which a given
$\mathcal{C}_{\textnormal{IS}}(T)$ routes flow to each
$\mathcal{C}_{\textnormal{IS}}(T^{\prime})$. We construct a flow in which for
every such
$\mathcal{C}_{\textnormal{IS}}(T),\mathcal{C}_{\textnormal{IS}}(T^{\prime})$,
every intermediate class $\mathcal{C}_{\textnormal{IS}}(T^{\prime\prime})$
that handles flow between sets $S\in\mathcal{C}_{\textnormal{IS}}(T)$ and
$S^{\prime}\in\mathcal{C}_{\textnormal{IS}}(T^{\prime})$ is larger than one of
$\mathcal{C}_{\textnormal{IS}}(T)$ or
$\mathcal{C}_{\textnormal{IS}}(T^{\prime})$. We then bound the number of pairs
of sets, relative to $|\mathcal{C}_{\textnormal{IS}}(T^{\prime\prime})|$, for
which $\mathcal{C}_{\textnormal{IS}}(T^{\prime\prime})$ carries flow.

To accomplish this, we observe that for any
$\mathcal{C}_{\textnormal{IS}}(T),\mathcal{C}_{\textnormal{IS}}(T^{\prime})$
such that there exists _one_ move between an independent set in
$\mathcal{C}_{\textnormal{IS}}(T^{\prime})$ and an independent set in
$\mathcal{C}_{\textnormal{IS}}(T)$, either _every_ independent set in
$\mathcal{C}_{\textnormal{IS}}(T^{\prime})$ has a move to some independent set
in $\mathcal{C}_{\textnormal{IS}}(T)$, or vice versa. This move consists of
dropping some vertex $v$ from $T^{\prime}\subseteq X$ to obtain $T$, i.e.
$T=T^{\prime}\setminus\\{v\\}$. We call $\mathcal{C}_{\textnormal{IS}}(T)$ a
_parent_ of $\mathcal{C}_{\textnormal{IS}}(T^{\prime})$, and
$\mathcal{C}_{\textnormal{IS}}(T^{\prime})$ a _child_ of
$\mathcal{C}_{\textnormal{IS}}(T)$. See Figure 3. Since the set of edges
connecting vertices in $\mathcal{C}_{\textnormal{IS}}(T)$ with vertices in
$\mathcal{C}_{\textnormal{IS}}(T^{\prime})$ forms a matching, this implies
that
$|\mathcal{C}_{\textnormal{IS}}(T)|\geq|\mathcal{C}_{\textnormal{IS}}(T^{\prime})|$.
In fact, whenever $T\subseteq T^{\prime}$, we have
$|\mathcal{C}_{\textnormal{IS}}(T)|\geq|\mathcal{C}_{\textnormal{IS}}(T^{\prime})|$.
We route flow between any pair of classes $\mathcal{C}_{\textnormal{IS}}(T)$
and $\mathcal{C}_{\textnormal{IS}}(T^{\prime})$ along a path through a “least
common ancestor”. Since for every class
$\mathcal{C}_{\textnormal{IS}}(T^{\prime\prime})$ on this path, either
$|\mathcal{C}_{\textnormal{IS}}(T^{\prime\prime})|\geq|\mathcal{C}_{\textnormal{IS}}(T)|$
or
$|\mathcal{C}_{\textnormal{IS}}(T^{\prime\prime})|\geq|\mathcal{C}_{\textnormal{IS}}(T^{\prime})|$,
we obtain a bound on congestion that we make precise in Appendix F.

In the proof sketch of Lemma 3.11 (Section 3.2), for every pair
$S\in\mathcal{C}_{\textnormal{}}(T),S^{\prime}\in\mathcal{C}_{\textnormal{}}(T^{\prime})\neq\mathcal{C}_{\textnormal{}}(T)$,
we found a sequence of classes
$\mathcal{C}_{\textnormal{}}(T)=\mathcal{C}_{\textnormal{}}(T_{1}),\mathcal{C}_{\textnormal{}}(T_{2}),\dots,\mathcal{C}_{\textnormal{}}(T_{k-1}),\mathcal{C}_{\textnormal{}}(T_{k})=\mathcal{C}_{\textnormal{}}(T^{\prime})$
through which to route the $S-S^{\prime}$ flow. As discussed in Section 4,
when the degree is unbounded, the classes are no longer nearly the same
size—so if this sequence is chosen carelessly, some
$\mathcal{C}_{\textnormal{}}(T_{i})$ may carry flow for too many
$S-S^{\prime}$ pairs. We therefore choose the sequences carefully: the parent-
child relationships induce a partial order $\prec$ on the classes with a
unique maximal element, where
$\mathcal{C}_{\textnormal{}}(T)\succ\mathcal{C}_{\textnormal{}}(T^{\prime})$
implies
$|\mathcal{C}_{\textnormal{}}(T)|\geq|\mathcal{C}_{\textnormal{}}(T^{\prime})|$.
We choose our sequence so that for some $i$ with $1\leq i\leq k$,
$|\mathcal{C}_{\textnormal{}}(T_{1})|\leq|\mathcal{C}_{\textnormal{}}(T_{2})|\leq\cdots\leq|\mathcal{C}_{\textnormal{}}(T_{i})|\geq|\mathcal{C}_{\textnormal{}}(T_{i+1})|\geq\cdots|\mathcal{C}_{\textnormal{}}(T_{k-1})|\geq|\mathcal{C}_{\textnormal{}}(T_{k})|$.

###  4.3 Hierarchical Framework Conditions

The conditions are as follows. Conditions 2 through 4 are new and concern the
partial order described above; Condition 1 and Conditions 5 through 7 are as
in Section 3.3.

  1. 1.

The vertices of $\mathcal{M}_{\textnormal{}}(G)$ can be partitioned into a set
$\mathcal{S}$ of classes, where $|\mathcal{S}|=O(1).$

  2. 2.

There exists a partial order $\prec$ on the classes in $\mathcal{S}$, such
that whenever
$\mathcal{C}_{\textnormal{}}(T),\mathcal{C}_{\textnormal{}}(T^{\prime})\in\mathcal{S}$
and
$\mathcal{C}_{\textnormal{}}(T)\succ\mathcal{C}_{\textnormal{}}(T^{\prime})$,
we have
$|\mathcal{C}_{\textnormal{}}(T)|\geq|\mathcal{C}_{\textnormal{}}(T^{\prime})|$.

  3. 3.

The partial order $\prec$ has a unique maximal element.

  4. 4.

Whenever an edge exists between vertices in $\mathcal{C}_{\textnormal{}}(T)$
and $\mathcal{C}_{\textnormal{}}(T^{\prime})$ with
$\mathcal{C}_{\textnormal{}}(T)\succ\mathcal{C}_{\textnormal{}}(T^{\prime})$,
the number of such edges is $|\mathcal{C}_{\textnormal{}}(T^{\prime})|$.

  5. 5.

For every pair of classes $\mathcal{C}_{\textnormal{}}(T)$ and
$\mathcal{C}_{\textnormal{}}(T^{\prime})$ that share an edge, the maximum
degree, in $\mathcal{C}_{\textnormal{}}(T)$, of a vertex in
$\mathcal{C}_{\textnormal{}}(T^{\prime})$, is $O(1)$, and the maximum degree,
in $\mathcal{C}_{\textnormal{}}(T^{\prime})$, of a vertex in
$\mathcal{C}_{\textnormal{}}(T)$, is $O(1)$.

  6. 6.

Each class in $\mathcal{S}$ is the Cartesian product of two graphs
${\mathcal{M}_{\textnormal{}}(G_{1})}$ and
$\mathcal{M}_{\textnormal{}}(G_{2})$, each of which can be recursively
partitioned in the same way as $\mathcal{M}_{\textnormal{}}(G)$.

  7. 7.

The recursive partitioning mentioned in Condition 6 reaches the base case
(graphs with one or zero vertices) in $O(\log n)$ levels of recursion.

######  Lemma 4.1.

Given a graph $\mathcal{M}_{\textnormal{}}(G)$ satisfying the conditions in
Section 4.3, the expansion of $\mathcal{M}_{\textnormal{}}(G)$ is
$\Omega(1/n^{c})$, where $c=O(1)$.

We defer the proof of Lemma 4.1 to Appendix F.

##  Appendix A Discussion of method and open questions

###  A.1 Application to graphical models

Prior work [9, 23] has shown that related chains, including _softcore models_
—in which the sampled sets need not be independent—mix rapidly on graphs of
bounded treewidth. However, all of the Glauber dynamics we consider pertain to
combinatorial sampling problems, in which one is sampling a subset of either
the vertices or the edges of a graph, where the subsets must obey certain
constraints, e.g. independence. As a result, and as Bordewich and Kang [9]
note, their technique does not extend to these models.

Similarly, in the setting of probabilistic graphical models, De Sa, Zhang,
Olukotun, and Ré [14] considered graphs with bounded _hierarchy width_. They
showed—via arguments similar to the projection-restriction technique [30]—that
graphs with logarithmically bounded hierarchy width admit rapid mixing for the
Glauber dynamics on models with bounded _maximum factor weight_. It is
straightforward to apply their argument to the _Ising_ and _Potts_ models with
fixed parameters, on graphs of bounded treewidth and degree. This case of
these models also admits application of projection-restriction (and in the
special case of the path graph Jerrum, Sinclair, Tetali, and Vigoda observed
this for the Ising model [30]), and it fits our framework. Since our framework
does not give a substantial improvement on existing results for these models,
we do not address them in detail in this paper; we simply note that the
framework we developed in our prior work [18] applies to these cases and to
every undirected graphical model having only pairwise and unary factors,
bounded maximum factor weights, constantly many values for each random
variable, and bounded treewidth and degree. This shows that the framework
unifies these models—in which all states have positive probability and which
prior work has addressed in these graphs—with combinatorial chains where some
states have zero probability—for which our results are new. We give a brief
sketch of how to apply our framework in Appendix G.2.2. See Bordewich,
Greenhill, and Patel [8] and Chen, Liu, and Vigoda [13] for definitions of and
results for these models.

###  A.2 Comparison with the projection-restriction technique

In the special cases of the hardcore model, $q$-colorings, and partial
$q$-colorings—as well as the bounded-treewidth-and-degree case of $b$-edge
covers and $b$-matchings, one could reframe our inductive step in terms of the
projection-restriction technique of Jerrum, Son, Tetali, and Vigoda [30].
Furthermore, as we have noted, Heinrich [28] used the projection-restriction
technique for $q$-colorings.

Indeed, the initial framework conditions we summarized in Section 3.3 are seen
to imply rapid mixing—provided an additional mild condition is satisfied—using
the projection-restriction technique, as we observed in our companion paper.
The idea is to first partition the Glauber graph into classes, each of which
is a Cartesian product of smaller Glauber graphs over an underlying graph at
most half the size of the original graph—just as we have done. One then
defines a _projection_ Markov chain whose states are identified with the
classes, where each class has probability mass proportional to its
cardinality. The transition probabilities between classes are then
proportional to the numbers of edges between classes (up to normalization by
the degree of each boundary vertex).

If one then finds a good upper bound on the mixing times of both the
projection chain and each of the individual class chains, one can derive a
good upper bound on the mixing time of the original chain. One then needs
either to incur an $O(1)$ congestion factor at each inductive step of the
decomposition, combined with an $O(\log n)$ induction depth—or alternatively
to bound a particular quantity $\gamma$ that describes, essentially, the
number of edges between any given class and the rest of the graph.

To find such an upper bound, one could naturally view our “classes” as
individual states in the projection chain, with probability masses
proportional to their cardinalities. Our construction of flow between classes
would become, under this view, a multicommodity flow in the projection chain.

However, as discussed in the introduction, constructing the flow in the
projection chain still requires showing that each chain satisfies the
framework conditions—and in the case of the hardcore model and dominating
sets, one needs the hierarchical framework conditions. Furthermore, as
formulated by Jerrum, Son, Tetali, and Vigoda [30], the projection-restriction
technique requires that the decomposition be a partition of the state space.
By contrast, we deal with several chains in which the “classes” overlap or are
internally not Cartesian products: namely dominating sets, $b$-edge covers
(when the degree is unbounded), maximal independent sets, and maximal
$b$-matchings. For these chains, our flow analysis provides a finer mechanism
for dealing with these structural challenges.

Thus we present our construction purely in combinatorial terms—as opposed to
considering a flow in a projection state space—for two key reasons: (i) to
deal with non-independence as in the third and fourth of our main theorems,
and (ii) because we believe our construction makes the graphical analysis of
these chains more intuitive.

###  A.3 Further discussion of prior work

Sly [50] showed that, except for restricted values of $\lambda<1$, the
hardcore model approximate sampling problem (obtaining an FPRAS) is hard (and
thus the Glauber dynamics does not mix rapidly) on general graphs unless RP =
NP. More precisely, Sly showed hardness when
$\lambda_{c}<\lambda<\lambda_{c}+\varepsilon$ where $\lambda_{c}$ is a certain
_uniqueness threshold_ that depends on the degree of the input graph. Sly and
Sun [51] and independently Galanis, Štefankovič, and Vigoda [22] later proved
hardness for all $\lambda>\lambda_{c}$. On the other hand, Anari, Liu, and
Oveis Gharan [1] used a technique known as _spectral independence_ to obtain
rapid mixing for the hardcore Glauber dynamics when $\lambda$ is below the
uniqueness threshold. They showed, by exhibiting an infinite family of
examples, that the technique they used could not be further improved (namely
beyond the uniqueness threshold) even for trees. By contrast, we show that
rapid mixing, for all fixed values of $\lambda$, indeed holds not only for
trees but for all graphs of bounded treewidth. Chen, Liu, and Vigoda [12]
showed $O(n\log n)$ mixing for bounded-degree graphs when
$\lambda<\lambda_{c}-\varepsilon$ for every $\varepsilon>0$, with a dependence
on $\varepsilon$ in the mixing time. Chen, Galanis, Štefankovič, and Vigoda
[11] generalized the technique of Anari, Liu, and Oveis Gharan to all 2-spin
systems; Feng, Guo, Yin, and Zhang [20] applied it to graph colorings.

Other results exist for trees beyond the uniqueness threshold, however:
Martinelli, Sinclair, and Weitz [37] showed that the dynamics on $q$-colorings
($q\geq\Delta+2$) mixes in $O(n\log n)$ time on the complete $\Delta-1$-ary
tree with $n$ nodes. Lucier, Molloy, and Peres [35] showed that the dynamics
mixes rapidly on general trees of bounded degree, namely in time
$O(n^{O(1+\Delta/(q\log\Delta))})$. Restrepo, Štefankovič, Vigoda, and Yang
[44] showed that for certain trees the mixing time slows down when $\lambda$
is sufficiently large.

Prior work also exists for $q$-colorings of bounded-treewidth graphs: Berger,
Kenyon, Mossel, and Peres [4] showed rapid mixing for $q$-colorings of regular
trees with unbounded degree. Tetali, Vera, Vigoda, and Yang [52] gave upper
and lower bounds for complete trees. Vardi [53] showed that the so-called
_single-flaw_ dynamics—a variaton on the Glauber dynamics in which at most one
monochromatic edge is permitted in a valid state—mixes rapidly on bounded-
treewidth graphs when $q\geq(1+\varepsilon)\Delta$, for any fixed parameter
$\varepsilon>0$. The proof used the vertex separaton properties of bounded-
treewidth graphs to construct a multicommodity flow with bounded congestion,
although the construction was substantally different from our divide-and-
conquer approach. Dyer, Goldberg, and Jerrum [15] showed rapid mixing when the
degree of the graph is at least $2t$ and $q\geq 4t$, where $t$ is the
treewidth. On the other hand, Heinrich [28] showed that the Glauber dynamics
on $q$-colorings of a bounded-treewidth graph mixes rapidly when
$q\geq\Delta+2$. Our construction, as we will discuss in more detail in
Section 1.4, bears some similarity to Heinrich’s. We also require that $q$
(and therefore $\Delta$) be bounded. However, due to a more general analysis
of the state spaces of Glauber dynamics as graphs, we obtain a more general
framework that holds for a greater variety of chains. We obtain an improvement
over [15] and [28] in the dependence on treewidth when $\Delta<2t$ or when
$q<4t$ and $\Delta<t^{2}$. We additionally show that the Glauber dynamics on
the _partial_ $q$-colorings of $G$ mix rapidly for all fixed $\lambda>0$ when
$q\geq\Delta+2$ is bounded.

Planar graphs have unbounded but sublinear treewidth. For planar graphs, Hayes
[26] showed that the Glauber dynamics on $q$-colorings of a planar graph of
maximum degree $\Delta$ mixes rapidly when $q\geq\Delta+O(\sqrt{\Delta})$.
Later, Hayes, Vera, and Vigoda [27] proved rapid mixing for $q$-colorings of
planar graphs when $q=\Omega(\Delta/\log\Delta)$, generalizing further to a
spectral condition on the adjacency matrix of the graph.

Bezáková and Sun showed [6] that the hardcore model mixes rapidly in chordal
graphs with bounded-size separators. Lastly, Chen, Galanis, Štefankovič, and
Vigoda applied the spectral independence technique to prove that the Glauber
dynamics on the $q$-colorings of a triangle-free graph with dgree $\Delta$
mixes rapidly provided that $q\geq\alpha\Delta+1$, where $\alpha$ is greater
than a threshold approximately equal to $1.763$. We show that when the
treewidth and degree of $G$ are bounded, $G$ need not be triangle free, and it
suffices that $q\geq\Delta+2$ be bounded. We prove a similar result for the
natural Glauber dynamics on _partial_ $q$-colorings.

Although our mixing results are new, Wan, Tu, Zhang, and Li showed [54] that
exact counting of independent sets is fixed-parameter tractable in treewidth.
Furthermore, our result does not technically constitute a proof of fixed-
parameter tractability, as the treewidth appears in the exponent of the
polynomial we obtain. For this problem and all the other problems we consider,
the problem of exact counting—and therefore also uniform sampling—has already
been solved on the graphs we consider by an extension of Courcelle’s theorem
[43]. In fact, the standard reduction from approximate sampling to approximate
counting [49] gives a somewhat different rapidly mixing Markov chain on a
larger state space. Nonetheless, our result does settle the question of rapid
mixing for a natural chain, and it implies a simpler scheme for approximately
sampling independent sets than one would obtain via this reduction.

Such a scheme is known as a _fully polynomial randomized approximation scheme
(FPRAS)_. Huang, Lu, and Zhang provided an FPRAS for sampling $b$-edge covers
in general graphs when $b\leq 2$, and for sampling $b$-matchings when $b\leq
7$ [29]. This FPRAS relied on a rapid mixing argument for a somewhat different
Markov chain than ours. Existing dominating set results for certain regular
graphs are also known [5].

Exact counting of maximal independent sets—which would give an FPRAS by the
equivalence of counting and sampling—was shown in [42] to be hard for chordal
graphs but is known [10] to be tractable in graphs of bounded treewidth.
However, again our result improves on the simplicity of existing algorithms.

Our approach is also inspired by Kaibel’s [31] construction of a flow with
bounded congestion in any graph whose vertices are hypercube vertices and
whose edges can be partitioned into bipartite graphs in a hierarchical
fashion.

###  A.4 Open questions

We have developed a framework whose application shows rapid mixing for several
natural chains on combinatorial structures in graphs of bounded treewidth.
However, some work is required in showing that each of the structures
satisfies the conditions of the framework. We hope that a more robust version
of the framework can be developed that further unifies these techniques.

In particular, all of the structures we have analyzed satisfy the conditions
of Courcelle’s theorem, as noted previously. It would be interesting to
determine whether the framework can be extended to all structures satisfying
these conditions.

The fact that our results hold for all values of $\lambda>0$ is not especially
surprising, as Ioannis Panageas has observed, since the limiting case
$\lambda=\infty$ corresponds to the optimization version of each problem, and
the case $\lambda=1$ corresponds to uniform sampling; as stated in the
introduction, both of these problems are already known to be fixed-parameter
tractable in treewidth. (In fact, as we noted in the introduction, the
extension of Courcelle’s theorem, combined with the reduction from sampling to
counting, applies to all values of $\lambda>0$.) Nonetheless, our result does
settle a missing case of the mixing question in some generality, through
purely combinatorial methods.

In all of our mixing bounds, the dependency on the parameters—treewidth and
degree—is bad. It would be interesting to see whether some refinement of our
methods could give a truly fixed-parameter tractable result, in which the
treewidth and degree do not appear in the exponent of $n$.

##  Appendix B Carving width

Since the present paper concerns bounded-treewidth and bounded-degree graphs,
we note the equivalence between these properties and a parameter known as
_carving width._ The carving width of a graph is a density parameter that is
weaker than treewidth, in the sense that high treewidth implies high carving
width, but the converse is not true. Carving width is defined with respect to
a so-called _carving decomposition_ [16] of a given graph $G$—in short, a
binary tree $T$ whose leaves are identified with the vertices of $G$. Each
node $X\in T$ is identified with the subgraph of $G$ induced by the vertices
of $G$ (leaves of $T$) having $X$ as an ancestor in $T$. Each edge of $T$
induces a cut in $T$; this cut induces a partition of the leaves of $T$
(vertices of $G$) into two sets. This partition is naturally identified with a
cut in $G$.

The _width_ of a carving decomposition is the maximum number of edges of $G$
across any such cut, where the maximum is taken over all edges in $T$. The
_carving width_ of $G$ is the minimum width of a carving decomposition of $G$.
See Seymour and Thomas [47] for a detailed treatment. For our purposes,
carving width is of interest due to its relationship to the treewidth and
degree of a graph. Specifically, Eppstein [16] observed the following fact
that follows from results of Nestoridis and Thilikos [41] and of Robertson and
Seymour [46]:

######  Lemma B.1.

Given a graph $G$ with maximum degree $\Delta$, let $\operatorname{tw}(G)$
denote the treewidth of $G$, and let $\operatorname{cw}(G)$ denote the carving
width of $G$. For every graph $G$,
$(2/3)(\operatorname{tw}(G)+1)\leq\operatorname{cw}(G)\leq\Delta(\operatorname{tw}(G)-1)$.

It follows from the definition of carving width that every graph with bounded
carving width also has bounded degree. Combining this fact with Lemma B.1
implies the following:

######  Corollary B.2.

A graph has bounded degree and treewidth if and only if it has bounded carving
width.

##  Appendix C Additional Chain Definitions

###  C.1 Dominating sets, maximal independent sets, $b$-matchings, and
$b$-edge covers

######  Definition C.1.

A _dominating set_ in a graph $G=(V,E)$ is a set $S\subseteq V$ of vertices
such that for every vertex $v\in V$, either $v\in S$ or there exists some
vertex $u\in S$ such that $(u,v)\in E$.

$b$-matchings [33] and $b$-edge covers [21, 32] generalize the definitions of
matchings and edge covers respectively:

######  Definition C.2.

Let $G=(V,E)$ be a graph. Let $b:V\rightarrow\mathbb{Z}^{\geq 0}$ be any
function assigning a nonnegative integer to each vertex. A _$b$ -matching_ in
a graph $G=(V,E)$ is a set $S\subseteq E$ of edges such that every $v\in V$
has at most $b(v)$ incident edges in $S$.

######  Definition C.3.

Let $G=(V,E)$ be a graph. Let $b:V\rightarrow\mathbb{Z}^{\geq 0}$ be any
function assigning a nonnegative integer to each vertex. A _$b$ -edge cover_
in a graph $G=(V,E)$ is a set $S\subseteq E$ of edges such that every $v\in V$
has at least $b(v)$ incident edges in $S$.

Sometimes, as in the result by Huang, Lu, and Zhang [29], $b$-edge covers and
$b$-matchings are defined so that $b$ is a constant, i.e. $b(u)=b(v)$ for all
$u,v\in V$.

For dominating sets, $b$-edge covers, and $b$-matchings, we consider a chain
similar to the hardcore dynamis in Definition 2.1, except that in the case of
$b$-edge covers and $b$-matchings, we are of course selecting edges instead of
vertices. Also, in the case of dominating sets and $b$-edge covers, instead of
verifying independence before _adding_ a vertex (or edge), we verify validity
of a set (e.g. domination) before _dropping_ a vertex (or edge).

We also consider the Glauber dynamics on _$q$ -colorings_:

######  Definition C.4.

A _$q$ -coloring_ of a graph $G$ is an assignment of a color from the list
$[q]=\\{1,2,\dots,q\\}$ to each vertex of $G$, such that no two adjacent
vertices have the same color.

######  Definition C.5.

A _partial $q$-coloring_ of a graph $G$ is an assignment of a color from $[q]$
to each of a subset of the vertices of $G$, such that no two adjacent vertices
have the same color.

The Glauber dynamics on the partial $q$-colorings of $G$ is as follows:

######  Definition C.6.

Let the Glauber dynamics on the partial $q$-colorings of a graph $G$ be the
following chain defined with respect to $\lambda>0$:

  1. 1.

Let $X_{0}$ be an arbitrary partial $q$-coloring of $G$.

  2. 2.

For $t\geq 0$, select a vertex $v\in V(G)$ uniformly at random, and select a
color $c\in[q+1]$ uniformly at random.

  3. 3.

If $c=q+1$, then:

If $v$ is already colored in $X_{t}$, remove the coloring of $v$ with
probability $1/(\lambda+1)$.

Otherwise, let $X_{t+1}=X_{t}$.

  4. 4.

If $c\leq q$, then:

If $v$ is _not_ already colored with $c$ in $X_{t}$, set the color of $v$ to
$c$ with probability $\lambda/(\lambda+1)$.

Otherwise, let $X_{t+1}=X_{t}$.

Finally, the Glauber dynamics on the (complete) $q$-colorings of $G$ is as
follows (for this chain we do not define a biased version):

######  Definition C.7.

Let the Glauber dynamics on the $q$-colorings of a graph $G$ be the following
chain:

  1. 1.

Let $X_{0}$ be an arbitrary $q$-coloring of $G$.

  2. 2.

For $t\geq 0$, select a vertex $v\in V(G)$ uniformly at random, and select a
color $c\in[q]$—other than the color of $v$—uniformly at random.

  3. 3.

If $v$ has no neighbor with color $c$, then change the color of $v$ to $c$
with probability 1/2 to obtain $X_{t+1}$.

  4. 4.

Otherwise, do nothing, i.e. let $X_{t+1}=X_{t}$.

We define a graph whose vertices are the maximal independent sets of an
underlying graph $G$, and then define the chain as a random walk on this
graph:

######  Definition C.8.

Given a graph $G=(V,E)$, let the _maximal independent set Glauber graph_ be
the graph $\mathcal{M}_{\textnormal{MIS}}(G)$ whose vertices are the maximal
independent sets of $G$, and whose edges are the pairs of maximal independent
sets that differ by one _move_ , where a move is defined as:

  1. 1.

adding one vertex $v$ to a given independent set $S\subseteq V$,

  2. 2.

removing every $u\in S$ such that $(u,v)\in E$, and

  3. 3.

adding a subset of the vertices at distance two in $G$ from $v$.

Since $\mathcal{M}_{\textnormal{MIS}}(G)$ is undirected, we also define the
reversal of a move as a move. See Figure 4 for an example of a move.

######  Lemma C.9.

The graph $\mathcal{M}_{\textnormal{MIS}}(G)$ in Definition C.8 is connected.

######  Proof C.10.

The proof relies on an easy greedy transformation argument and is in Appendix
I.

For maximal $b$-matchings, we define a Glauber graph similar to the maximal
independent set Glauber graph, except that we are of course selecting edges
instead of vertices in our sets. A move consists of adding some edge $e=(u,v)$
to the $b$-matching, then removing edges incident to $u$ and $v$ as needed
until a valid $b$-matching is obtained, then adding edges incident to
neighbors of $u$ and $v$ as needed to obtain maximality.

##  Appendix D Derivation of upper bounds in main theorems

We now analyze the specific polynomial upper bounds that we obtain from each
version of the framework.

In the following bounds, we consider all logarithms to be base two, unless
otherwise stated. The $\log n$ terms in the exponents of these bounds come
from the balanced separators guaranteed by bounded treewidth. Technically, as
we have defined balanced separators, one of the two mutually disconnected
subgraphs obtained by removing a balanced separator may have size greater than
$n/2$. However, one can show [19] that no _connected component_ of the
resulting disconnected graph has size greater than $n/2$. It is
straightforward to modify many of our proofs to account for Cartesian products
with multiple factor graphs, by iterating Lemma 3.10. When this is not
possible, we will explicitly state the base we use.

We proved the following in our companion paper [18]:

######  Lemma D.1.

Suppose a Glauber graph $\mathcal{M}_{\textnormal{}}(G)$ satisfies the
conditions of the non-hierarchical framework. Then the mixing time of the
corresponding Glauber dynamics is

$O((2N/\mathcal{E}_{\min})+1)^{2\log n}\cdot\Delta_{\mathcal{M}}^{2}\log N),$

where $\mathcal{E}_{\min}$ is the size of the smallest edge set between
adjacent classes.

######  Proof D.2.

The idea of the proof, which we gave in our companion paper, is that there
exists a uniform multicommodity flow in which no matching
$\mathcal{E}_{\textnormal{}}(T,T^{\prime})$ carries more than $N^{2}$ un-
normalized flow, since this is the total amount of flow to be exchanged in the
uniform multicommodity flow. Therefore each vertex in each class
$\mathcal{C}_{\textnormal{}}(T)$ brings in at most $2N^{2}/\mathcal{E}_{\min}$
un-normalized flow across all of its edges out of
$\mathcal{C}_{\textnormal{}}(T)$ combined. The result then follows from using
the inductively defined flow within $\mathcal{C}_{\textnormal{}}(T)$ to route
this flow, with the factor of 2 coming from accounting for both “inbound” and
“outbound” flow, and with the $2\log n$ exponent and the
$\Delta_{\mathcal{M}}^{2}\log N$ terms coming from the squaring that takes
place in Lemma 3.8.

The arXiv version we have cited gives a term $4N/\mathcal{E}_{\min}$ instead
of the $2N/\mathcal{E}_{\min}$ term we have given here. A newer version of the
companion paper has the latter bound. To obtain the improvement, it suffices
to take the proof in the arXiv version [17], Lemma 7.1, and observe that the
incoming “through” flow described, combined with the inbound flow, can only
sum to $N^{2}/(|\mathcal{E}_{\textnormal{}}(T,T^{\prime})|$ units.

In the case of $q$-colorings, tracing the constant factors in the proof of
Lemma E.3, we see that $N/\mathcal{E}_{\min}\leq q^{2\Delta(t+1)},$ that
$\Delta_{\mathcal{M}}\leq(q-1)n$, and that $N\leq q^{n}$. Combining this with
Lemma 3.8 and Lemma 3.9 gives the bound claimed in Theorem 1.2. More
precisely, the bound is

$((2(q^{2\Delta(t+1)})+1)^{2\log n})=O((q-1)^{2}\log q\cdot
n^{4(t+1)\Delta\log q+7}).$

We will prove the following in Appendix F:

######  Lemma D.3.

Suppose a Glauber graph $\mathcal{M}_{\textnormal{}}(G)$ satisfies the
conditions of the hierarchical framework. Then the mixing time of the
corresponding Glauber dynamics is

$O(((2K+1)^{2\log n})\cdot\Delta_{\mathcal{M}}^{2}\log N),$

where $\Delta_{\mathcal{M}}$ is the maximum degree of the Glauber graph
$\mathcal{M}_{\textnormal{}}(G)$, $n=|V(G)|$, $K$ is the number of classes in
the partition, and $N=|V(\mathcal{M}_{\textnormal{}}(G))|$.

The unbiased case of the bound in Theorem 1.1 now follows from combining Lemma
D.3 with the observation that for this chain, $\log N\leq n$,
$\Delta_{\mathcal{M}}=n$, and $K\leq 2^{t+1}$. Similarly, as we will see, the
bound for the unbiased case of partial $q$-colorings in Theorem 1.2 will
follow from the fact that $K\leq(q+1)^{t+1}$, $\Delta_{\mathcal{M}}\leq qn$,
and $N\leq(q+1)^{n}$, so that

$(2(K+1))^{2\log n}\Delta_{\mathcal{M}}^{2}\log
N=n^{2\log{2(K+1)}}\Delta_{\mathcal{M}}^{2}\log N$ $\leq q^{2}\log(q+1)\cdot
n^{2(t+2)\log(q+1)+5}.$

##  Appendix E Bounded treewidth and degree: application of framework beyond
independent sets

###  E.1 $q$-colorings

We now apply the non-hierarchical framework to $q$-colorings in graphs of
bounded treewidth and degree. For reasons that will soon become apparent, we
need to generalize to _list colorings_ :

######  Definition E.1.

A _list coloring_ of a graph $G=(V,E)$, given a function $L:V\rightarrow
2^{[q]}$ assigning a list of colors to each vertex in $V$, is a coloring of
$G$ consistent with $L$. A _partial list coloring_ is a coloring of some of
the vertices of $G$ consistent with $L$.

We consider the Glauber graph $\mathcal{M}_{\textnormal{COL}}(G,L)$, defined
as follows:

######  Definition E.2.

Let the Glauber graph $\mathcal{M}_{\textnormal{COL}}(G,L)$, given an input
graph $G$ and a set of colors $[q]$ and a function $L$ as in Definition E.1,
be the graph whose vertices are the list colorings of $G$ consistent with $L$,
and whose edges are the pairs of list colorings $C,C^{\prime}$ that differ by
a color assignment to exactly one vertex $v\in V(G)$.

The Glauber dynamics in Definition C.7 is the natural random walk on
$\mathcal{M}_{\textnormal{COL}}(G,L)$, with self-loops added in the standard
fashion. The following lemma therefore suffices to prove the first claim in
Theorem 1.2:

######  Lemma E.3.

$\mathcal{M}_{\textnormal{COL}}(G,L)$, defined over a graph $G$ and a list
$L:V(G)\rightarrow 2^{[q]}$, with $L(v)\geq\delta(v)+2$ for every $v\in V(G)$,
satisfies the conditions of the non-hierarchical framework whenever $G$ has
bounded treewidth and degree and $q$ is fixed.

######  Proof E.4.

We partition $V(\mathcal{M}_{\textnormal{COL}}(G,L))$ into classes induced by
a small balanced separator $X$, where each class is identified with a list
coloring $T$ of $G[X]$. This partitioning satisfies Condition 5 since each
class $\mathcal{C}_{\textnormal{COL}}(T)$ consists of the tuples of the form
$(C_{A},C_{B})$, where $C_{A}$ is a valid list coloring of $G[A]$, and $C_{B}$
is a valid list coloring of $G[B]$—with $A$ and $B$ being the mutually
disconnected subsets of $V(G)$ resulting from the removal of $X$. Here, we
adjust the list $L(u)$ for each $u\in N_{A}(X)\cup N_{B}(X),$ removing from
$L(u)$ every color that is assigned to a neighbor of $u$ in $X$ under the
coloring $C$.

The subproblems on $A$ and $B$ are independent, and that a move within
$\mathcal{C}_{\textnormal{COL}}(T)$ corresponds to a move within either $A$ or
$B$ but not both. Furthermore, the condition that $L(u)\geq\delta(u)+2$ is
preserved even after $L$ is modified, since every color removed from $L(u)$
corresponds to a neighbor of $u$ in $X$—i.e. a neighbor that is not part of
the subproblem on $A$ or $B$. Condition 5 follows.

Condition 1 follows from the fact that $|X|$ and $q$ are bounded. Condition 2
can be seen from the bounded treewidth and degree of $G$ by considering the
following mapping
$f:V(\mathcal{M}_{\textnormal{COL}}(G,L))\rightarrow\mathcal{C}_{\textnormal{COL}}(T)$
for any $T$: given a list coloring $C\in
V(\mathcal{M}_{\textnormal{COL}}(G,L))$, let $C^{\prime}=f(C)$ be the list
coloring that (i) agrees with $T$ on its restriction to $X$, (ii) agrees with
$C$ on its assignment of colors to all vertices having no neighbor in $X$, and
(iii) is consistent with both (i) and (ii) on its assignment of colors to
neighbors of vertices in $X$.

We can always satisfy (iii) because for each $u\in N_{A}(X)\cup N_{B}(X)$, we
have $|L(u)|\geq\delta(u)+2$. (There may be multiple list colorings satisfying
(iii); resolve ambiguity in defining $f(C)$ via an arbitrary ordering on the
list colorings of $G$.) Condition 4 follows from a similar mapping.

Condition 3 follows from the definition of a move; Condition 6 follows from
the bounded treewidth and degree of $G$.

###  E.2 $b$-edge covers and $b$-matchings

For $b$-edge covers and $b$-matchings, we now apply the non-hierarchical
framework in graphs of bounded treewidth and degree. As with independent sets,
dealing with unbounded degree in $b$-edge covers requires the hierarchical
framework.

######  Lemma E.5.

Given an input graph $G$ of bounded treewidth and degree, the Glauber dynamics
on $b$-matchings and on $b$-edge covers satisfy the conditions of the non-
hierarchical framework, when the maximum value of the function $b$ is bounded.

######  Proof E.6.

The proof for $b$-edge covers is similar to the proof of Lemma 3.7, with the
following modifications.

In defining a $b$-edge cover, we are selecting subsets of edges instead of
vertices. Thus, to define our chain on $b$-edge covers, we modify the chain on
independent sets in the natural way: dropping or adding edges instead of
vertices. The corresponding Glauber graph $\mathcal{M}_{\textnormal{BEC}}(G)$
is connected, since every $b$-edge cover has a path in
$\mathcal{M}_{\textnormal{BEC}}(G)$ to the trivial $b$-edge cover (where every
edge is selected). We identify each class $\mathcal{C}_{\textnormal{BEC}}(T)$
with the set $T$ of edges chosen incident to vertices in $X$. Since degree is
bounded and $|X|\leq t$, there are $O(1)$ classes, satisfying Condition 1.

Given a class $\mathcal{C}_{\textnormal{BEC}}(T)$, we pass recursively to
subproblems on $A$ and $B$, where we update $b(v)$ for each $v\in A\cup B$
according to the number of edges in $T$ incident to $v$. That is, for each
vertex $u$ selected in $T$, and for each edge $(u,v)$ with $v\in A$ (similarly
$v\in B$), decrement $b(v)$ when passing to the subproblem on $A$ (similarly
$B$). The choices made in the $A$ subproblem and the $B$ subproblem are
independent, giving the required Cartesian product structure for Condition 5,
and there are still $O(\log n)$ levels of recursion, satisfying Condition 6.
For Condition 3, the proof is the same as for independent sets. Conditions 2
and 4 follow from a similar mapping argument to that in the proof of Lemma
3.5.

The proof for $b$-matchings is similar to that for $b$-edge covers.

###  E.3 Maximal independent sets and maximal $b$-matchings

The main idea of applying the framework to maximal independent sets and
maximal $b$-matchings is similar to that for independent sets, $b$-matchings,
and $b$-edge covers, but some adaptation is required: the definition of a move
is somewhat different, and the proof that classes have the required Cartesian
product structure has a few more details. We thus defer dealing with these
chains to Appendix H.6.2.

##  Appendix F Hierarchical framework

In this section we complete the proof of the unbiased case of Theorem 1.1 and
Theorem 1.2, by fully specifying the hierarchical framework, and showing that
the chain on independent sets satisfies the conditions. Fully proving Theorem
1.3 and Theorem 1.4 requires some adaptation of the framework, which we defer
to Appendix H.

###  F.1 Proof that conditions of the hierarchical framework imply rapid
mixing

We are ready to prove the counterpart of Lemma 3.11 for the hierarchical
framework, from which the unbiased case of Theorem 1.1 will follow.

See 4.1

######  Proof F.1.

We use the scheme in the proof of Lemma 3.11, with the following
specification: when routing flow from $S\in\mathcal{C}_{\textnormal{}}(T)$ to
$S^{\prime}\in\mathcal{C}_{\textnormal{}}(T^{\prime})\neq\mathcal{C}_{\textnormal{}}(T)$,
we find a sequence of classes
$\mathcal{C}_{\textnormal{}}(T)=\mathcal{C}_{\textnormal{}}(T_{1}),\mathcal{C}_{\textnormal{}}(T_{2}),\dots,\mathcal{C}_{\textnormal{}}(T_{k-1}),\mathcal{C}_{\textnormal{}}(T_{k})=\mathcal{C}_{\textnormal{}}(T^{\prime})$
as before, where each consecutive pair of classes in the sequence shares an
edge in $\mathcal{M}_{\textnormal{}}(G)$. In the proof of Lemma 3.11, this
sequence was arbitrary; we now require that, under the partial order $\prec$
in Condition 2, for some $1\leq i\leq k$,
$\mathcal{C}_{\textnormal{}}(T_{1})\prec\cdots\prec\mathcal{C}_{\textnormal{}}(T_{i})\succ\mathcal{C}_{\textnormal{}}(T_{i+1})\succ\cdots\succ\mathcal{C}_{\textnormal{}}(T_{k})$;
Condition 3 guarantees that this requirement can be satisfied.

We now bound the resulting congestion. As in the proof of Lemma 3.11, for
$i=2,\dots,k-1$, the congestion added to edges in
$\mathcal{C}_{\textnormal{}}(T_{i})$ in the inductive step is at most
$N^{2}/(|Y_{i}||Z_{i}|)\cdot c^{\log n-1}$. Unfortunately, without assuming
that the classes are approximately the same size, we can no longer say that
$|Y_{i}|=\Omega(N)$ or $|Z_{i}|=\Omega(N)$. Instead, we argue as follows:
thanks to the choice of our sequence, for every pair of classes
$\mathcal{C}_{\textnormal{}}(T)$ and $\mathcal{C}_{\textnormal{}}(T^{\prime})$
that use a given class $T_{i}$ to route flow, either
$|\mathcal{C}_{\textnormal{}}(T_{i})|\geq|\mathcal{C}_{\textnormal{}}(T)|$
(and
$|\mathcal{C}_{\textnormal{}}(T_{i})|\geq|\mathcal{C}_{\textnormal{}}(T_{i-1})|$)
or
$|\mathcal{C}_{\textnormal{}}(T_{i})|\geq|\mathcal{C}_{\textnormal{}}(T^{\prime})|$
(and
$|\mathcal{C}_{\textnormal{}}(T_{i})|\geq|\mathcal{C}_{\textnormal{}}(T_{i+1})|$).
Assume the former case without loss of generality. For every pair of classes
$\mathcal{C}_{\textnormal{}}(T)$ and $\mathcal{C}_{\textnormal{}}(T^{\prime})$
that use the edges between $\mathcal{C}_{\textnormal{}}(T_{i-1})$ and
$\mathcal{C}_{\textnormal{}}(T_{i})$,
$|\mathcal{C}_{\textnormal{}}(T)|\leq|\mathcal{C}_{\textnormal{}}(T_{i-1})|$,
and therefore the number of pairs $S,S^{\prime}$ of Glauber graph vertices
that use these edges is at most

$\sum_{T,T^{\prime}:|\mathcal{C}_{\textnormal{}}(T)|\leq|\mathcal{C}_{\textnormal{}}(T_{i-1})|}|\mathcal{C}_{\textnormal{}}(T)||\mathcal{C}_{\textnormal{}}(T^{\prime})|\leq
N|\mathcal{S}||\mathcal{C}_{\textnormal{}}(T_{i-1})|=O(1)N|\mathcal{C}_{\textnormal{}}(T_{i-1})|.$

Therefore, since there are $|\mathcal{C}_{\textnormal{}}(T_{i-1})|$ edges
between $\mathcal{C}_{\textnormal{}}(T_{i-1})$ and
$\mathcal{C}_{\textnormal{}}(T_{i})$ (by Condition 4), each such edge carries
at most
$N|\mathcal{S}||\mathcal{C}_{\textnormal{}}(T_{i-1})|/|\mathcal{C}_{\textnormal{}}(T_{i-1})|=O(N)$
units of flow, giving $O(1)$ congestion.

To bound congestion within $\mathcal{C}_{\textnormal{}}(T_{i})$, we specify
the routing of flow from $\mathcal{Y}_{i}$ (the set of vertices on the
$\mathcal{C}_{\textnormal{}}(T_{i-1}),\mathcal{C}_{\textnormal{}}(T_{i})$
boundary) to $\mathcal{Z}_{i}$ (the set of vertices on the
$\mathcal{C}_{\textnormal{}}(T_{i}),\mathcal{C}_{\textnormal{}}(T_{i+1})$
boundary) as follows: first let each $Y\in\mathcal{Y}_{i}$ send an equal
fraction of its flow—of which it receives $O(N)$ units from each of $O(1)$
edges—to _every vertex in $\mathcal{C}_{\textnormal{}}(T_{i})$_, using
$\rho_{T_{i}}$ to route the flow. Then let each $Z\in\mathcal{Z}_{i}$ receive
its flow similarly from all vertices in $\mathcal{C}_{\textnormal{}}(T_{i})$.
The resulting congestion across each edge is at most

$(2O(N)/|\mathcal{C}_{\textnormal{}}(T_{i})|)\cdot c^{\log
n-1}|\mathcal{C}_{\textnormal{}}(T_{i})|/N\leq c^{\log n},$

for a constant $c$. This gives the desired congestion bound, proving the
lemma.

We now prove Lemma D.3 by tracing the polynomial factors in the proof of Lemma
4.1: See D.3

######  Proof F.2.

The analysis is similar to the proof of Lemma D.1, with the following
modifications: each edge set $\mathcal{E}_{\textnormal{}}(T,T^{\prime})$ from
$\mathcal{C}_{\textnormal{}}(T)$ to a parent
$\mathcal{C}_{\textnormal{}}(T^{\prime})$ has
$|\mathcal{E}_{\textnormal{}}(T,T^{\prime})|=|\mathcal{C}_{\textnormal{}}(T)|$.
Therefore, outbound flow along each edge in such an edge set is at most
$N|\mathcal{C}_{\textnormal{}}(T)|/|\mathcal{E}_{\textnormal{}}(T,T^{\prime})|=N$:
each vertex (all vertices in $\mathcal{C}_{\textnormal{}}(T)$ are boundary
vertices) then receives from each other vertex at most
$N/|\mathcal{C}_{\textnormal{}}(T)|$ units. As we will show shortly (see
analysis of through flow below), edges to children each carry at most
$K|\mathcal{C}_{\textnormal{}}(T)|$. Thus we will count the flow resulting
from edges to children with through flow.

Inbound flow is symmetric. The result is to scale the amount of flow across
each edge internal to $\mathcal{C}_{\textnormal{}}(T)$ by a factor of
$2N/|\mathcal{C}_{\textnormal{}}(T)|$.

For through flow (including the outbound flow to children as described above),
each boundary vertex in $\mathcal{C}_{\textnormal{}}(T)$ carrying flow from
(or to) a set of child classes
$\\{\mathcal{C}_{\textnormal{}}(T_{1}^{\prime}),\dots,\mathcal{C}_{\textnormal{}}(T_{k}^{\prime})\\}$
carries at most
$\sum_{i=1}^{k}N|\mathcal{C}_{\textnormal{}}(T_{i}^{\prime})/(|\mathcal{C}_{\textnormal{}}(T)|)\leq
NK_{i}|\mathcal{C}_{\textnormal{}}(T)|/|\mathcal{C}_{\textnormal{}}(T)|$
units, where $K_{i}<K$ is the number of classes descendent from
$\mathcal{C}_{\textnormal{}}(T_{i}^{\prime})$, including
$\mathcal{C}_{\textnormal{}}(T_{i}^{\prime})$ itself. This sum is at most
$N(K-1)$. Each boundary vertex carrying flow from (or to) an ancestor
similarly carries at most $NK$ units. Thus through flow contributes a factor
of $2N(K-1)/|\mathcal{C}_{\textnormal{}}(T)|$.

The resulting overall congestion is therefore at most

$O((2K+1)^{2\log n}),$

where the extra $+1$ term comes from accounting for the congestion from
routing flow for pairs in the same class, and applying Lemma 3.9 and Lemma 3.8
gives the resulting mixing bound.

###  F.2 Independent sets

We now finish the proof of the unbiased case of Theorem 1.1.

####  F.2.1 Verification of conditions

To show that the chain on independent sets satisfies the conditions of the
hierarchical framework when treewidth is bounded (but degree is unbounded), we
first define a partial order $\prec$ on the classes in
$\mathcal{S}_{\textnormal{IS}}(G)$. Recall (Definition 3.3) that these are the
classes induced by the separator $X$ in the underlying graph $G$.

######  Definition F.3.

For
$\mathcal{C}_{\textnormal{IS}}(T),\mathcal{C}_{\textnormal{IS}}(T^{\prime})\in\mathcal{S}_{\textnormal{IS}}(G)$,
let
$\mathcal{C}_{\textnormal{IS}}(T)\prec\mathcal{C}_{\textnormal{IS}}(T^{\prime})$
if $T\subseteq T^{\prime}$ and $T\neq T^{\prime}$. Call
$\mathcal{C}_{\textnormal{IS}}(T)$ an _ancestor_ of
$\mathcal{C}_{\textnormal{IS}}(T^{\prime})$, and
$\mathcal{C}_{\textnormal{IS}}(T^{\prime})$ a _descendant_ of
$\mathcal{C}_{\textnormal{IS}}(T)$. If $\mathcal{C}_{\textnormal{IS}}(T)$
covers $\mathcal{C}_{\textnormal{IS}}(T^{\prime})$ in this relation, call
$\mathcal{C}_{\textnormal{IS}}(T)$ a _parent_ of
$\mathcal{C}_{\textnormal{IS}}(T^{\prime})$, and
$\mathcal{C}_{\textnormal{IS}}(T^{\prime})$ a _child_ of
$\mathcal{C}_{\textnormal{IS}}(T)$.

We now prove that the chain on independent sets satisfies the conditions of
the hierarchical framework on graphs of bounded treewidth.

######  Lemma F.4.

Given a graph $G$ with fixed treewidth $t-1$, the hardcore Glauber dynamics on
the independent sets of $G$ satisfies the conditions of the hierarchical
framework.

######  Proof F.5.

Let $\mathcal{M}_{\textnormal{IS}}(G)$, $X$, and
$\mathcal{S}_{\textnormal{IS}}(G)$ be as previously defined. We have already
proven Condition 1 and Conditions 4 through 7 in Lemmas 3.5 through 3.5.

The partial order in Definition F.3 satisfies Condition 2 because for every
parent class $\mathcal{C}_{\textnormal{IS}}(T)$ and child class
$\mathcal{C}_{\textnormal{IS}}(T^{\prime})$, the recursive subproblems in the
Cartesian product comprising $\mathcal{C}_{\textnormal{IS}}(T^{\prime})$ are
at least as constrained as the subproblems in the product comprising
$\mathcal{C}_{\textnormal{IS}}(T)$. That is,
$\mathcal{C}_{\textnormal{IS}}(T)$ and
$\mathcal{C}_{\textnormal{IS}}(T^{\prime})$ are each a Cartesian product of
two smaller Glauber graphs on the independent sets in subgraphs $A_{T}$ and
$B_{T}$ of $G$, and subgraphs $A_{T^{\prime}}$ and $B_{T^{\prime}}$ of $G$
respectively. We have $V(A_{T^{\prime}})\subseteq V(A_{T})$ and
$V(B_{T^{\prime}})\subseteq V(B_{T})$, where the set $V(A_{T})\setminus
V(A_{T^{\prime}})$ consists of the vertices in $A$ that have a neighbor in
$T^{\prime}$ but not in $T$.

Condition 3 follows from the fact that the empty independent set is the unique
set that is an ancestor of all other independent sets.

It now follows by Lemma 3.9 that $\mathcal{M}_{\textnormal{}}(G)$ has
expansion $\Omega(1/n^{O(1)})$, and Theorem 1.1 follows from this fact and
from Lemma 3.8. More precisely, observing that the number of classes in the
partition is at most $2^{t+1}$ and applying Lemma D.3 gives the bound claimed
in Theorem 1.1, namely

$O(((1+\hat{\lambda})\hat{\lambda})^{2}(1+\log\hat{\lambda})n^{2(t+2)(1+\log\hat{\lambda})+5}),$

where $\hat{\lambda}=\max\\{\lambda,1/\lambda\\}.$

###  F.3 Partial $q$-colorings

We now prove the unbiased case of the claim about partial colorings in Theorem
1.2:

######  Definition F.6.

Let $\mathcal{M}_{\textnormal{PCOL}}(G,L)$, given an input graph $G$ and
function $L:V(G)\rightarrow 2^{[q]}$, be the graph whose vertices are the
partial list colorings of $G$, and whose edges are the pairs of partial list
colorings that differ by the removal or addition of a color assignment to a
single vertex.

We show that this Glauber graph satisfies the conditions of the hierarchical
framework:

######  Lemma F.7.

Given a graph $G$ with bounded treewidth and degree and list function
$L:V(G)\rightarrow 2^{[q]}$, where $q\geq\Delta+2$ is fixed and
$L(v)\geq\delta(v)+2$ for all $v\in V(G)$, the Glauber graph
$\mathcal{M}_{\textnormal{PCOL}}(G,L)$ has expansion $\Omega(1/n^{c})$, where
$c=O(1)$.

######  Proof F.8.

The partitioning is the same as in the proof of Lemma E.3, except that we
allow each class to be identified with a partial list coloring of $X$.
Condition 1, Condition 5, Condition 6, and Condition 7 are as before. For
Conditions 2 and 3, the partial order is analogous to the partial order for
independent sets: given partial list colorings $C$ and $C^{\prime}$ of $X$,
let $C$ be a parent of $C^{\prime}$ if $C$ and $C^{\prime}$ agree except for a
single vertex to which $C^{\prime}$ assigns a coloring and $C$ does not.
Condition 4 follows from this definition. The lemma follows.

We obtain the bound in Theorem 1.2 via the observations in Section D.

##  Appendix G All $\lambda>0$

Until now, we have only considered the unbiased versions of our chains. In
this section we complete the proof of Theorem 1.1, for arbitrary fixed
$\lambda>0$. To do so, we need to introduce the standard notion of
_conductance_ [48], which extends the definition of expansion in the natural
way to the setting of a weighted graph.

###  G.1 (Weighted) Conductance

The conductance is defined with respect to a _stationary_ distribution $\pi$
induced by a random walk. The stationary distribution is the distribution to
which the random walk converges in the limit. The convergence requires mild
conditions: (i) that walk be _ergodic_ , meaning that the Glauber graph is
connected; (ii) that the walk be _reversible_ ; and (iii) that the walk be
_lazy_.

Laziness means that with constant probability the walk stays at the current
vertex at any step; reversibility means that for every pair of sets
$S,S^{\prime}\in\mathcal{M}_{\textnormal{IS}}(G)$, we have

$\pi(S)P(S,S^{\prime})=\pi(S^{\prime})P(S^{\prime},S),$

where $P(S,S^{\prime})$ denotes the probability that $X_{t+1}=S^{\prime}$,
given that $X_{t}=S$.

The Glauber dynamics on independent sets is known to satisfy these conditions,
and it is easy to show that our other Glauber dynamics satisfy them as well.

In the case of the Glauber dynamics on independent sets, the stationary
distribution $\pi$ evaluates to

$\pi(S)=\lambda^{|S|}/Z(\mathcal{M}_{\textnormal{IS}}(G)),$

where for each of our Glauber graphs $\mathcal{M}_{\textnormal{}}(G)$,

$Z(\mathcal{M}_{\textnormal{}}(G))=\sum_{S\subseteq
V(\mathcal{M}_{\textnormal{}}(G))}\lambda^{|S|}$

is the normalizing constant. For all independent sets $S$ in $G$, and for all
$S^{\prime}$ such that $|S\setminus S^{\prime}|=1,$ we have

$\pi(S)P(S,S^{\prime})=\pi(S^{\prime})P(S^{\prime},S)=(\frac{1}{n(1+\lambda)})(\frac{\lambda^{|S|}}{Z(\mathcal{M}_{\textnormal{IS}}(G))}),$

where $n=|V(G)|$.

For dominating sets and partial $q$-colorings, we define the same
distribution; for $b$-edge covers we define the analogous distribution over
edges.

######  Remark G.1.

For each of our Glauber graphs $\mathcal{M}_{\textnormal{}}(G)$, the
probability transition function $P(S,S^{\prime})$, viewed as a matrix, is in
fact the adjacency matrix of an edge-weighted version of
$\mathcal{M}_{\textnormal{}}(G)$, ignoring self loops.

That is:

######  Definition G.2.

Given a Glauber graph $\mathcal{M}_{\textnormal{}}(G)$ and a Markov chain on
$\mathcal{M}_{\textnormal{}}(G)$ with stationary distribution $\pi$ and
probability transition function $P$, assign the weight $\pi(S)$ to each vertex
$S$ of $\mathcal{M}_{\textnormal{}}(G)$, and assign the weight
$Q(S,S^{\prime})=\pi(S)P(S,S^{\prime})$ to each edge $(S,S^{\prime})$.

######  Definition G.3.

Extend the definition of a Cartesian graph product to the weighted graphs
described in this section, so that for vertices $g\in V(G),h\in V(H)$, the
weight of the tuple $(g,h)\in V(G\Box H)$ is $\pi(g,h)=\pi_{G}(g)\pi_{H}(h)$,
where $\pi_{G}$ and $\pi_{H}$ are the vertex weight functions for $G$ and $H$
respectively. Let the weight of each edge $e$ between $(g,h)$ and
$(g^{\prime},h^{\prime})$ be

$Q(e)=\pi_{H}(h)(\Delta_{G}Q_{G}(g,g^{\prime}))/(\Delta_{G}+\Delta_{H}),$

if $g\neq g^{\prime}$ and $h=h^{\prime}$, and

$Q(e)=\pi_{G}(g)(\Delta_{H}Q_{H}(h,h^{\prime}))/(\Delta_{G}+\Delta_{H}),$

if $g=g^{\prime}$ and $h\neq h^{\prime}$, where $Q_{G}$ and $Q_{H}$ are the
edge weight functions for $G$ and $H$, and $\Delta_{G}$ and $\Delta_{H}$ are
the maximum degrees of $G$ and $H$.

For the self loop $e=((g,h),(g,h)),$ let

$Q(e)=\pi(g,h)-\sum_{(g^{\prime\prime},h):g^{\prime\prime}\neq
g}Q((g,h),(g^{\prime\prime},h))-\sum_{(g,h^{\prime\prime}):h^{\prime\prime}\neq
h}Q((g,h),(g,h^{\prime\prime})),$

######  Lemma G.4.

Given Definition G.3, the stationary distribution $\pi$ in the discussion
leading to Remark G.1, and the resulting vertex and edge weights as in
Definition G.2, for each of our Glauber graphs
$\mathcal{M}_{\textnormal{}}(G)$ and for each class
$\mathcal{C}_{\textnormal{}}(T)\cong\mathcal{M}_{\textnormal{}}(A)\Box\mathcal{M}_{\textnormal{}}(B)$,
and for each $S\in V(\mathcal{M}_{\textnormal{}}(A)),S^{\prime}\in
V(\mathcal{M}_{\textnormal{}}(B))$, the following facts hold:

  1. 1.

The vertex weight of $S\cup S^{\prime}\cup T$ in
$\mathcal{M}_{\textnormal{}}(G)$ is equal to

$\pi_{\mathcal{M}_{\textnormal{}}(G)}(S\cup S^{\prime}\cup
T)=\pi_{\mathcal{C}_{\textnormal{}}(T)}(S,S^{\prime})\pi_{\mathcal{M}_{\textnormal{}}(G)}(\mathcal{C}_{\textnormal{}}(T)),$

where $\pi_{\mathcal{M}_{\textnormal{}}(G)}(\mathcal{C}_{\textnormal{}}(T))$
is defined as
$\sum_{U\in\mathcal{C}_{\textnormal{}}(T)}\pi_{\mathcal{M}_{\textnormal{}}(G)}(U)$,
and

  2. 2.

For all $S^{\prime\prime}$ with $|S\setminus S^{\prime\prime}|=1$, the weight
in $\mathcal{M}_{\textnormal{}}(G)$ of the edge $e$ between $S\cup
S^{\prime}\cup T$ and $S^{\prime\prime}\cup S^{\prime}\cup T$ is

$Q_{\mathcal{M}_{\textnormal{}}(G)}(e)=Q_{\mathcal{C}_{\textnormal{}}(T)}(e)\pi_{\mathcal{M}_{\textnormal{}}(G)}(\mathcal{C}_{\textnormal{}}(T))\frac{|V(A)|+|V(B)|}{|V(G)|}.$

######  Proof G.5.

We have

$\frac{\lambda^{|S|+|S^{\prime}|+|T|}}{Z(\mathcal{M}_{\textnormal{}}(G))}=\pi_{\mathcal{M}_{\textnormal{}}(A)}(S)\pi_{\mathcal{M}_{\textnormal{}}(B)}(S^{\prime})\lambda^{|T|}\cdot\frac{Z(\mathcal{M}_{\textnormal{}}(A))Z(\mathcal{M}_{\textnormal{}}(B))}{Z(\mathcal{M}_{\textnormal{}}(G))}=\pi_{\mathcal{C}_{\textnormal{}}(T)}(S,S^{\prime})\pi_{\mathcal{M}_{\textnormal{}}(G)}(\mathcal{C}_{\textnormal{}}(T)),$

and

$Q(e)=\frac{1}{|V(G)|(\lambda+1)}\cdot\frac{\lambda^{|S|+|S^{\prime}|+|T|}}{Z(\mathcal{M}_{\textnormal{}}(G))}=Q_{\mathcal{M}_{\textnormal{}}(A)}(S,S^{\prime\prime})\pi_{\mathcal{M}_{\textnormal{}}(B)}(S^{\prime})\lambda^{|T|}\cdot\frac{Z(\mathcal{M}_{\textnormal{}}(A))Z(\mathcal{M}_{\textnormal{}}(B))}{Z(\mathcal{M}_{\textnormal{}}(G))}\cdot\frac{|V(A)|}{|V(G)|}$
$=Q_{\mathcal{C}_{\textnormal{}}(T)}(e)\lambda^{|T|}\cdot\frac{Z(\mathcal{M}_{\textnormal{}}(A))Z(\mathcal{M}_{\textnormal{}}(B))}{Z(\mathcal{M}_{\textnormal{}}(G))}\cdot\frac{|V(A)|+|V(B)|}{|V(G)|}$
$=Q_{\mathcal{C}_{\textnormal{}}(T)}(e)\pi_{\mathcal{M}_{\textnormal{}}(G)}(\mathcal{C}_{\textnormal{}}(T))\frac{|V(A)|+|V(B)|}{|V(G)|}.$

######  Definition G.6.

Given a lazy, reversible, ergodic random walk on a weighted graph
$\mathcal{M}=(\mathcal{V},\mathcal{E})$ with stationary distribution $\pi$ and
probability matrix $P:\mathcal{V}\times\mathcal{V}\rightarrow[0,1]$, the
_conductance_ is the quantity

$\phi(\mathcal{M})=\min_{\mathcal{S}\subseteq\mathcal{V}:0<\pi(\mathcal{S})\leq
1/2}\frac{Q(\mathcal{S},\mathcal{V}\setminus\mathcal{S})}{\pi(\mathcal{S})},$

where for sets $\mathcal{S},\mathcal{S}^{\prime}\subseteq\mathcal{V}$,

$\pi(\mathcal{S})=\sum_{S\in\mathcal{S}}\pi(S),$

and

$Q(\mathcal{S},\mathcal{S}^{\prime})=\sum_{S\in\mathcal{S},S^{\prime}\in\mathcal{S}^{\prime}}Q(S,S^{\prime}),$

and where $Q(S,S^{\prime})=\pi(S)P(S,S^{\prime})$ given
$S,S^{\prime}\in\mathcal{V}$.

We now extend the definitions of multicommodity flows and congestion:

######  Definition G.7.

Let a multicommodity flow $\rho$ in a graph
$\mathcal{M}=(\mathcal{V},\mathcal{E})$ be defined as before, except that each
pair of vertices $S,S^{\prime}\in\mathcal{V}$ exchanges
$\pi(S)\pi(S^{\prime})$ units of flow in each direction. Let

$\rho_{max}=\sum_{e\in\mathcal{E}}\frac{\rho(e)}{Q(e)}.$

The following generalizations of Lemma 3.9 and Lemma 3.8 relate the
conductance, congestion, and mixing time [48]:

######  Theorem G.8.

Given a multicommodity flow $\rho$ in a graph $\mathcal{M}$, the conductance
$\phi$ satisfies $\phi\geq 1/(2\rho)$.

######  Theorem G.9.

The mixing time of a Markov chain with state space $\Omega$, stationary
distribution $\pi^{*}$, and conductance at least $\phi$ is at most

$\tau(\varepsilon)=O(\phi^{-2}\log(1/(\pi_{\min}^{*}\cdot\varepsilon))),$

where

$\pi_{\min}^{*}=\min_{u\in\Omega}\pi^{*}(u).$

###  G.2 Analysis of flow construction

We now complete the proof of Theorem 1.1. It suffices to show the following
lemma:

######  Lemma G.10.

The flow $\rho$ constructed in $\mathcal{M}_{\textnormal{IS}}(G)$ in the proof
of Lemma 4.1, adjusted so that $\mathcal{M}_{\textnormal{IS}}(G)$ is weighted
according to the parameter $\lambda>0$, and so that each pair of sets
$S,S^{\prime}$ exchanges $\pi(S)\pi(S^{\prime})$ units of flow as in
Definition G.7, results in a congestion factor gain of at most
$\rho_{\max}=O(1)$ at each of the $O(\log n)$ levels of induction, resulting
in at most polynomial overall congestion. The same holds for the chain on
partial $q$-colorings.

######  Proof G.11.

We use the same inductive argument, with the following adjustment: if
$\mathcal{C}_{\textnormal{}}(T)$ is a descendant of
$\mathcal{C}_{\textnormal{}}(T_{i-1})$, and
$\mathcal{C}_{\textnormal{}}(T_{i-1})$ is a child of
$\mathcal{C}_{\textnormal{}}(T_{i})$, where $\mathcal{C}_{\textnormal{}}(T)$
uses the edges between $\mathcal{C}_{\textnormal{}}(T_{i-1})$ and
$\mathcal{C}_{\textnormal{}}(T_{i})$ to send flow to
$\mathcal{C}_{\textnormal{}}(T^{\prime})$, then distribute this flow as before
across these edges, but now let each edge carry flow in proportion to its
weight. We have
$\pi(\mathcal{C}_{\textnormal{}}(T))=O(1)\pi(\mathcal{C}_{\textnormal{}}(T_{i-1}))$—because
for every independent set $S\in\mathcal{C}_{\textnormal{}}(T)$ there exists a
distinct independent set $S^{\prime}\in\mathcal{C}_{\textnormal{}}(T_{i-1})$
with $\pi(S^{\prime})=(1/\lambda^{|T\setminus T_{i-1}|})\pi(S)$, namely
$S^{\prime}=S\setminus(T\setminus T_{i-1})$.

Each edge $(S,S^{\prime})$ with
$S\in\mathcal{C}_{\textnormal{}}(T_{i}),S^{\prime}\in\mathcal{C}_{\textnormal{}}(T_{i-1})$,
satisfies $Q(S,S^{\prime})=\Omega(\pi(S)/n)$ (where the constant-factor
difference depends on $\lambda$). Thus the congestion along these edges is
still $O(n)$. We then allow each vertex
$S\in\mathcal{C}_{\textnormal{}}(T_{i})$, having received at most $O(\pi(S))$
units along each of $O(1)$ incoming edges from child classes, to distribute
these units to all other vertices in $\mathcal{C}_{\textnormal{}}(T_{i})$
according to their weight. That is, let $S$ send
$O(\pi(S)\pi(S^{\prime\prime})/\pi(\mathcal{C}_{\textnormal{}}(T_{i})))$ units
to each $S^{\prime\prime}\in\mathcal{C}_{\textnormal{}}(T_{i})$. By the
inductive hypothesis and Lemma 3.10, a flow $\rho_{T_{i}}$ already exists
under which $S$ sends
$\pi(S)\pi(S^{\prime\prime})/(\pi(\mathcal{C}_{\textnormal{}}(T_{i})))^{2}$
units to $S^{\prime\prime}$ at a congestion cost of $O(nc^{\log n-1})$, for
appropriate constant $c$. Thus letting $S$ send
$O(\pi(S)\pi(S^{\prime\prime})/\pi(\mathcal{C}_{\textnormal{}}(T_{i})))$ units
to $S^{\prime\prime}$ reduces the amount sent across each edge by at least a
factor of $1/\pi(\mathcal{C}_{\textnormal{}}(T_{i}))$, while the weight of
each edge increases when passing from the factor graphs of
$\mathcal{C}_{\textnormal{}}(T_{i})$ to $\mathcal{M}_{\textnormal{}}(G)$ by at
most the same factor—up to the change in degree of the Glauber graph—by Lemma
G.4. This gives congestion cost at most $O(nc^{\log n})$.

####  G.2.1 Specific polynomial bounds

We now revisit the discussion in Section D. In Theorem 1.1, the
$1+\log\hat{\lambda}$ term in the exponent comes from observing that, in Lemma
D.3, we can replace the $K+1$ term with $K\lambda^{t+1}+1$ —since in the proof
of Lemma D.3, this is the factor by which the flow carried into a class from a
child class increases when adjusting for the weights induced by the parameter
$\lambda$. A similar analysis gives the result for partial $q$-colorings in
Theorem 1.2.

####  G.2.2 The Ising and Potts models

As we discussed in the introduction, one can apply our framework to the Ising
and Potts models when the parameters of these models are fixed. We do not give
the standard definitions of these models or a detailed proof. Instead, we
simply observe that in a graph of bounded treewidth and degree, the same
decomposition technique given in the non-hierarchical framework applies, with
the following modification. Since all assignments of spins are possible, so
instead of considering the cardinalities of the sets we consider weights of
configurations under the standard (exponentiated) energy functions. It is easy
to verify the conditions under this modification, using the insight that the
weights of the classes differ by a constant factor from one another, since
this factor is determined only by evaluating the energy function at a constant
number of edges and vertices.

##  Appendix H Dealing with non-independence

The Glauber dynamics on independent sets induces a Glauber graph,
$\mathcal{M}_{\textnormal{IS}}(G)$, that behaves well when partitioned into
classes. That is, each class $\mathcal{C}_{\textnormal{IS}}(T)$ is isomorphic
to the Cartesian product of two Glauber graphs on subgraphs of $G$. As we will
see in Appendix F, the Glauber dynamics on partial $q$-colorings is similarly
well-behaved. Unfortunately, as we will discuss in Appendix H, this does not
hold for dominating sets or, in the unbounded-degree case, for $b$-edge
covers. In these problems, the selection $T\subseteq X$ of vertices (or edges)
in the separator $X$ with which the class $\mathcal{C}_{\textnormal{}}(T)$ is
identified imposes constraints on what vertices (or edges) can be chosen in
the two subgraphs $A\cup B=G\setminus X$—and choices in $A$ may invalidate
those in $B$.

In the case of maximal independent sets and maximal $b$-matchings, the
situation is worse: the classes induced by selection of $T\subseteq X$ may not
even be internally connected.

We address both of these problems by relaxing the framework condition that
each class $\mathcal{C}_{\textnormal{}}(T)$ be a Cartesian product of Glauber
graphs, and instead require that each class $\mathcal{C}_{\textnormal{}}(T)$
be the (not necessarily disjoint) union of Cartesian products of Glauber
graphs, satisfying certain conditions. We fully specify this condition, and
show that the remaining chains satisfy it, this section. That is, we complete
the proofs of Theorem 1.3 and Theorem 1.4. The principal problem is that when
attempting to partition the Glauber graph into classes as we did for
independent sets, the resulting classes are not isomorphic to Cartesian
products of Glauber graphs. For instance, in the case of $b$-edge covers, we
wish to identify a class of $b$-edge covers with the set $T$ of edges selected
within the subgraph of $G$ induced by the separator $X$. Unfortunately, the
resulting subproblems on $A$ and $B$ (where, as before, $A\cup B=V(G)\setminus
X$) are not independent. This is because for each vertex $x\in X$, the sum of
the number of incident edges selected in $A$ and those in $B$ must be at least
$b(x)$, so the choices made in $A$ depend on those made in $B$, and vice
versa.

The solution is as follows: we divide each class into smaller (not necessarily
disjoint) “subclasses”, each of which is a Cartesian product of smaller
Glauber graphs on $b$-edge covers. We detail this in Appendix H.2.

We encounter a similar problem in the case of dominating sets, with an
additional challenge that will require us to generalize the definition of a
dominating set into what we call the “constrained Steiner dominating set”
problem. We give the full details in Appendix H.3.

For maximal independent sets and maximal $b$-matchings (Appendix H.6), the
non-hierarchical framework is more natural, as we require bounded degree. The
challenge is twofold: first, we need to define the Glauber graphs and show
that they are connected. Secondly, we need to deal with non-independence as
with $b$-edge covers and dominating sets—with the additional challenge, as we
will see, that the classes are not necessarily internally connected.

###  H.1 Framework relaxation to allow non-independence

######  Lemma H.1.

Suppose a Glauber graph $\mathcal{M}_{\textnormal{}}(G)$ satisfies the
conditions of the hierarchical framework in Appendix 4.3, except for Condition
6. Suppose further that each class
$\mathcal{C}_{\textnormal{}}(T)\in\mathcal{S}$ is the union of at most $O(1)$
subclasses
$\mathcal{C}_{\textnormal{}}(T)=\mathcal{C}_{\textnormal{}}(T_{1})\cup\mathcal{C}_{\textnormal{}}(T_{2})\cup\cdots\mathcal{C}_{\textnormal{}}(T_{k})$,
where for $i=1,\dots,k-1$:

  1. 1.

$|\mathcal{C}_{\textnormal{}}(T_{i})|=\Theta(1)|\mathcal{C}_{\textnormal{}}(T_{i+1})|$,
and

  2. 2.

$\mathcal{C}_{\textnormal{}}(T_{i})$ and
$\mathcal{C}_{\textnormal{}}(T_{i+1})$ share at least
$\Omega(1)|\mathcal{C}_{\textnormal{}}(T_{i})|=\Omega(1)|\mathcal{C}_{\textnormal{}}(T_{i+1})|$
vertices.

Suppose further that for $i=1,\dots,k$, $\mathcal{C}_{\textnormal{}}(T_{i})$
is isomorphic to the Cartesian product of two Glauber graphs
$\mathcal{M}_{\textnormal{}}(G_{1})$ and $\mathcal{M}_{\textnormal{}}(G_{2})$,
each of which can be recursively partitioned in the same way as
$\mathcal{M}_{\textnormal{}}(G)$.

Then the expansion of $\mathcal{M}_{\textnormal{}}(G)$ is $\Omega(1/n^{c})$,
where $c=O(1)$.

######  Proof H.2.

It suffices to construct a multicommodity flow among the subclasses in
$\mathcal{S}_{\textnormal{}}(T)$ and bound its congestion. By the inductive
hypothesis and Lemma 3.10, each subclass $\mathcal{C}_{\textnormal{}}(T_{i})$
has an internal flow $\rho_{T_{i}}$ with congestion $\rho_{T_{i}\max}\leq
c^{\log n-1}$. We would like to derive a flow $\rho_{T}$ with congestion
$\rho_{T\max}\leq c^{\log n-1}$; this will allow the rest of the proof of
Lemma 4.1 to be applied.

The solution is to follow the proof sketch of Lemma 3.7: for Glauber graph
vertices
$S\in\mathcal{C}_{\textnormal{}}(T_{i}),S^{\prime}\in\mathcal{C}_{\textnormal{}}(T_{j})\neq\mathcal{C}_{\textnormal{}}(T_{i})$,
send the $S-S^{\prime}$ flow through the classes
$\mathcal{C}_{\textnormal{}}(T_{i+1}),\mathcal{C}_{\textnormal{}}(T_{i+1}),\dots,\mathcal{C}_{\textnormal{}}(T_{j-1})$.
For $l=i,\dots,j$, let $\mathcal{Y}_{l}$ and $\mathcal{Z}_{l}$ be as in the
proof of Lemma 3.7, except that $Z_{l}=Y_{l+1}$. That is, the boundary
vertices in consecutive pairs of classes on the path are shared between the
two classes. The routing of flow within each class on the path is the same as
in Lemma 3.7.

The resulting congestion bound is the same as in Lemma 3.7. The only concern
is that since the subclasses may not be disjoint, each edge within a subclass
may incur congestion from multiple steps on the path. However, because the
number of classes is $O(1)$, there are $O(1)$ such steps, and thus the factor
by which this increases congestion is $O(1)$.

###  H.2 $b$-edge covers in the relaxed hierarchical framework

To finish the proof of Theorem 1.3, it now suffices to show that the chains on
dominating sets and $b$-edge covers satisfy the conditions of the hierarchical
framework when treewidth is bounded. We begin with $b$-edge covers.

Let $\mathcal{C}_{\textnormal{BEC}}(T)$ be defined as in Section E.2, with the
following modification: define each class $\mathcal{C}_{\textnormal{BEC}}(T)$
so that $T$ is identified with the set of selected edges _both of whose
endpoints_ are in $X$, instead of including all edges incident to vertices in
$X$.

We now divide each class $\mathcal{C}_{\textnormal{BEC}}(T)$ into subclasses.
For each $x\in X$, let $\delta_{T}(x)$ be the number of edges incident to $x$
(from neighbors in $X$) that are selected in $T$. Let
$b^{\prime}(x)=b(x)-\delta_{T}(x)$, i.e. decrease $b(x)$ by the number of
edges incident to $x$ selected in $X$. For each $x\in X$, every valid $b$-edge
cover in $T$ includes numbers of edges from neighbors in $A$ and $B$ that sum
to at least $b^{\prime}(x)$.

We will define a subclass of $\mathcal{C}_{\textnormal{BEC}}(T)$ for each
possible assignment of $b$-values to the vertices in $X$ in the subproblems on
$A$ and $B$. (The number of these subclasses, since $|X|=O(1)$ and $b$ is
bounded, is still $O(1)$.)

Formally:

######  Definition H.3.

Define functions $\beta$ and $\overline{\beta}$ as any assignments of
$b$-values, in the subproblems on $A$ and $B$ respectively, to all vertices
$x\in X$, such that the $\beta$ and $\overline{\beta}$ values sum to
$b^{\prime}(x)$ for each $x$.

There are many degrees of freedom in defining $\beta$. Consider each possible
choice of $\beta$ and $\overline{\beta}$.

######  Definition H.4.

Define the subclass $\mathcal{C}_{\textnormal{BEC}}(T_{\beta})$ as the set of
all $b$-edge covers that consist of a $\beta$-edge cover in $A$ and a
$\overline{\beta}$-edge cover in $B$.

That is, in class $\mathcal{C}_{\textnormal{BEC}}(T_{\beta})$, for each $x$,
the number of incident edges selected in $A$ is at least $\beta(x)$, and the
number of incident edges in $B$ is at least $\overline{\beta}(x)$.

Each of these subclasses $\mathcal{C}_{\textnormal{BEC}}(T_{\beta})$ is a
Cartesian product of $b$-edge cover Glauber graphs, over subgraphs $A$ and $B$
of $G$, and thus internally has a good flow $\rho_{\beta}$; thus it suffices
to combine flows within these subclasses together to design a flow $\rho_{T}$
in $\mathcal{C}_{\textnormal{BEC}}(T)$. We can then apply the hierarchical
framework to obtain the desired flow in $\mathcal{M}_{\textnormal{BEC}}(G)$.

######  Lemma H.5.

Given a graph $G$ and corresponding Glauber graph
$\mathcal{M}_{\textnormal{BEC}}(G)$, each class
$\mathcal{C}_{\textnormal{BEC}}(T)$ of $b$-edge covers in
$\mathcal{M}_{\textnormal{BEC}}(G)$ satisfies the conditions of Lemma H.1.

######  Proof H.6.

The number of subclasses is $O(1)$. The subclasses are also all within an
$O(1)$ size factor of one another. To see this, compare
$|\mathcal{C}_{\textnormal{BEC}}(T)|$ and
$|\mathcal{C}_{\textnormal{BEC}}(T_{\beta})|$, for any $\beta$. Fix some
lexicographic ordering of the edges of $G$. For every $b$-edge cover
$S\in\mathcal{C}_{\textnormal{BEC}}(T)$, there exists a $b$-edge cover
$S^{\prime}\in\mathcal{C}_{\textnormal{BEC}}(T_{\beta})$ that includes the
lexicographically first $\beta(x)$ edges in $A$ incident to $x$, for each
$x\in X$, and also includes the first $\overline{\beta}(x)$ edges in $B$
incident to $x$. (Let $S^{\prime}$ agree with $S$ on all other edges.) This is
a $2^{b}$-to-1 mapping, i.e. an $O(1)$-to-1 mapping.

Finally, every pair of subclasses overlaps in at least
$\Omega(1)|\mathcal{C}_{\textnormal{BEC}}(T)|$ vertices: consider the set of
all $b$-edge covers in $\mathcal{C}_{\textnormal{BEC}}(T)$ in which for each
$x\in X$, $x$ has $\min\\{b^{\prime}(x),\delta_{A}(x)\\}$ incident edges
selected in $A$, and $\min\\{b^{\prime}(x),\delta_{B}(x)\\}$ incident edges
selected in $B$. The number of such $b$-edge covers is
$\Omega(1)|\mathcal{C}_{\textnormal{BEC}}(T)|$, by similar reasoning to the
above; furthermore, every pair of subclasses of
$\mathcal{C}_{\textnormal{BEC}}(T)$ contains this set of $b$-edge covers. The
lemma follows.

The rest of the hierarchical framework conditions are easy to verify, and thus
the result in Theorem 1.3 for the unbiased case of $b$-edge covers follows.
The specific bound follows from the following observations: first,
constructing the flow within a class $\mathcal{C}_{\textnormal{BEC}}(T)$
incurs a factor of

$2L|\mathcal{C}_{\textnormal{BEC}}(T)|/(\nu(\min_{\beta}|\mathcal{C}_{\textnormal{BEC}}(T_{\beta})|)),$

where $\nu$ is the minimum fraction of vertices shared by a pair of adjacent
classes whose intersection is used in the flow, $L$ is the maximum number of
subclasses that a vertex can belong to, and
$\min_{\beta}|\mathcal{C}_{\textnormal{BEC}}(T_{\beta})|$ is the smallest
subclass of $\mathcal{C}_{\textnormal{BEC}}(T)$. $L$ is at most the number of
subclasses, which is upper-bounded by $(b+1)^{t+1}$; the smallest subclass has
size at least $|\mathcal{C}_{\textnormal{BEC}}(T)|/2^{b(t+1)}$; and $\nu\geq
1/2.$ (The latter two facts follow readily from observations made in the proof
of Lemma H.5.)

Thus the construction of the flow within $\mathcal{C}_{\textnormal{BEC}}(T)$
incurs a factor of at most $4(b+1)^{t+1}\cdot 2^{b(t+1)}$. In the biased chain
the overlap between adjacent subclasses is at least $\lambda/(1+\lambda)$
instead of $1/2$, and we need to adjust the ratio
$|\mathcal{C}_{\textnormal{BEC}}(T)|/|\mathcal{C}_{\textnormal{BEC}}(T_{\beta})|$
by a factor of $\hat{\lambda}^{b(t+1)}.$ Therefore this expression becomes

$2\frac{1+\lambda}{\lambda}(b+1)^{t+1}\cdot(2\hat{\lambda})^{b(t+1)}.$

The rest of the inductive step is as in the case of independent sets, i.e. we
apply Lemma D.3, using $K\leq 2^{t(t+1)/2},$ $\Delta_{\mathcal{M}}\leq m$, and
$N\leq 2^{m}$. (In the weighted case,
$\pi_{\min}^{*}\leq(2\hat{\lambda})^{m}.$ When considering $K$ in the
application of Lemma D.3, we need to weight $K$ by a factor of
$\hat{\lambda}^{t(t+1)/2}$.

Thus we obtain an additional factor of

$2(K\hat{\lambda}^{t(t+1)/2}+1)\leq 2((2\hat{\lambda})^{t(t+1)/2+1}).$

Altogether, these two flow constructions combined, in each iteration, result
in a factor of at most

$4(\frac{1+\lambda}{\lambda})(b+1)^{t+1}\cdot(2\hat{\lambda})^{(t+1)(b+t/2)+1}.$

The resulting mixing time is therefore at most

$O(((1+\hat{\lambda})\hat{\lambda})^{2}m^{3}(\log\hat{\lambda}+1)n^{2(2+\log(1+\lambda)-\log(\lambda)+(t+1)\log(b+1)+((t+1)(b+t/2)+1)(1+\log\hat{\lambda}))}).$

We have ignored one detail: technically the number of levels of induction is
greater than $\log n$, because the $t+1$ vertices in the separator are
included in the independent subproblems within each subclass. Furthermore, we
cannot assume that we have two connected components of size at most $|V(G)|/2$
at each level of decomposition, so the base of the log is 3/2 and not 2.

However, for every $\varepsilon<1/2,$ we have for all $n\geq(t+1)/\varepsilon$
that $2n/3+t+1\leq n(2/3+\varepsilon)$. Thus at the cost of a base case for
the induction of $(2\hat{\lambda})^{((t+1)/\varepsilon)^{2}}$, we adjust the
$\log n$ exponent in the congestion term to $\log_{1/(2/3+\varepsilon)}n$.
Letting $\varepsilon=1/6$, we obtain the mixing bound claimed in Theorem 1.3,
namely

$O\left(((2\hat{\lambda})^{36(t+1)^{2}})^{2}\left(\frac{\hat{\lambda}}{(1+\hat{\lambda})}\right)^{2}m^{3}(\log\hat{\lambda}+1)n^{\frac{2(3+\log(1+\lambda)-\log(\lambda)+(t+1)\log(b+1)+((t+1)(b+t/2)+1)(1+\log\hat{\lambda}))}{\log(6/5)}}\right).$

###  H.3 Dominating sets in the relaxed hierarchical framework

To finish the proof of Theorem 1.3 in the unbiased case, we now deal with
dominating sets.

As with $b$-edge covers, defining classes in the same way as in the case of
independent sets does not result in Cartesian products of dominating set
Glauber graphs, because it may be that some vertices in $X$ are not dominated
by vertices in $T\cap X$; these vertices must then be dominated by vertices in
$A$ or in $B$.

Therefore, to preserve the recursive structure of the problem and thus
complete the proof of Theorem 1.3, we define the _constrained Steiner
dominating set problem_ as a generalization of the dominating set problem, in
which there are three types of vertices:

  1. 1.

“normal” vertices, which must be dominated and may be selected in a dominating
set,

  2. 2.

“Steiner” vertices, which need not be dominated and may be selected, and

  3. 3.

“forbidden” vertices, which must be dominated and must not be selected.

Now, we let $X$ be a balanced vertex separator in $G$ as before. We would like
to define each class $\mathcal{C}_{\textnormal{DOM}}(T)$ by a choice of
vertices in $X$. In the resulting subproblem in $A$ (similarly $B$), we then
designate each vertex $v\in A\cup B$ having a neighbor selected in $T\subseteq
X$ as Steiner. However, there may be vertices in $X$ that are not selected or
dominated by any vertex in $T$. To obtain a valid dominating set, some
neighbor of each such vertex $w$ must be chosen in either $A$ or $B$. Thus we
have non-independent subproblems, which ruins the Cartesian product structure
needed for the divide-and-conquer argument. To resolve this non-independence,
we divide $\mathcal{C}_{\textnormal{DOM}}(T)$ into subclasses as follows:

######  Definition H.7.

Given a graph $G$, separator $X$, and CSDS Glauber graph
$\mathcal{M}_{\textnormal{DOM}}(G)$, and class
$\mathcal{C}_{\textnormal{DOM}}(T)$ of CSDS’s in
$\mathcal{M}_{\textnormal{DOM}}(G)$, let $U$ be the set of undominated
vertices in $X$ in class $\mathcal{C}_{\textnormal{DOM}}(T)$. For each subset
$W\subseteq U$, let the subclass $\mathcal{C}_{\textnormal{DOM}}(T_{W})$ be
the set of all CSDS’s that consist of a union of a CSDS on $A\cup W$, and a
CSDS on $B\cup U\setminus W$—in which each $w\in W$ is a forbidden vertex in
the $A$ subproblem, and each $\overline{w}\in U\setminus W$ is a forbidden
vertex in the $B$ subproblem.

There are at most $2^{t}=O(1)$ such subclasses. Technically, as with $b$-edge
covers, these are not equivalence classes, as some CSDS solutions may belong
to multiple classes. We will address this shortly, but first we specify how to
route flow among the subclasses within $\mathcal{C}_{\textnormal{DOM}}(T)$.
Once we have specified this flow, we can simply apply the flow described in
the proof of Lemma 4.1 to route flow among the “main” classes.

######  Lemma H.8.

Given a graph $G$, corresponding CSDS Glauber graph
$\mathcal{M}_{\textnormal{DOM}}(G)$, and a class
$\mathcal{C}_{\textnormal{DOM}}(T)$ of CSDS’s in
$\mathcal{M}_{\textnormal{DOM}}(G)$, the partition into subclasses given in
Definition H.7 satisfies the conditions of Lemma H.1.

######  Proof H.9.

There are $O(1)$ classes. We observe that the subclasses are all within an
$O(1)$ size factor of one another. To see this, compare the sizes of
$\mathcal{C}_{\textnormal{DOM}}(T)$ and
$\mathcal{C}_{\textnormal{DOM}}(T_{W})$. Since
$\mathcal{C}_{\textnormal{DOM}}(T_{W})\subseteq\mathcal{C}_{\textnormal{DOM}}(T)$,
$|\mathcal{C}_{\textnormal{DOM}}(T_{W})|\leq\mathcal{C}_{\textnormal{DOM}}(T)$.
On the other hand, consider the mapping that sends every CSDS
$s\in\mathcal{C}_{\textnormal{DOM}}(T)$ to a CSDS
$s^{\prime}\in\mathcal{C}_{\textnormal{DOM}}(T_{W})$ in which at least one
neighbor (say, the first lexicographically) of each $w\in W$ is selected in
$A$, and in which the first neighbor of each $\overline{w}\in U\setminus W$ is
selected in $B$. This mapping is $2^{|U|}$-to-1 $=O(1)$-to-1, and thus the
size factor difference is $O(1)$.

Now, since the subclasses are not equivalence classes, many pairs of
subclasses overlap. In particular, let $T$ and $U$ be as before, and suppose
for some $u\in U$, $W^{\prime}=W\cup\\{u\\}$. Then
$\mathcal{C}_{\textnormal{DOM}}(T_{W})$ and
$\mathcal{C}_{\textnormal{DOM}}(T_{W^{\prime}})$ overlap at those CSDS’s in
which some neighbor of $u$ in $A$ is selected, and some neighbor of $u$ in $B$
is selected. For every such pair of subclasses
$\mathcal{C}_{\textnormal{DOM}}(T_{W})$ and
$\mathcal{C}_{\textnormal{DOM}}(T_{W^{\prime}})$, at least half of the CSDS’s
in $\mathcal{C}_{\textnormal{DOM}}(T_{W})$ and at least half of those in
$\mathcal{C}_{\textnormal{DOM}}(T_{W^{\prime}})$ are part of the overlap.

$\mathcal{C}_{\textnormal{DOM}}(T)$ is internally connected via these
overlaps: every CSDS in $\mathcal{C}_{\textnormal{DOM}}(T)$ has a path to the
trivial CSDS in which every non-forbidden vertex of $A\cup B$ is selected.
Thus the conditions of Lemma H.1 are satisfied.

As in the discussion following Lemma H.5, we derive the bound in Theorem 1.3
as follows: the flow within a class incurs a congestion factor of

$2\frac{1+\lambda}{\lambda}\cdot(2\hat{\lambda})^{t+1}|\mathcal{C}_{\textnormal{DOM}}(T)|/(\min_{W}|\mathcal{C}_{\textnormal{DOM}}(T_{W})|)\leq
2\frac{1+\lambda}{\lambda}(4\hat{\lambda})^{t+1}.$

The application of Lemma D.3 contributes a $2(K\hat{\lambda}^{t+1}+1)$ factor
to the inductive step, with $K=2^{t+1}$.

Thus the factor for one iteration is at most

$4\frac{1+\lambda}{\lambda}(8\hat{\lambda}^{2})^{t+2}.$

The inclusion of the $t+1$ separator vertices in the subproblems, as with
$b$-edge covers, increases the induction depth, and an analogous analysis
gives a base case of $(2\hat{\lambda})^{6(t+1)}$ using $\varepsilon=1/6$.
Putting all this together with the fact that $\Delta_{\mathcal{M}}\leq n$ and
$1/\pi_{\min}^{*}\leq(2\hat{\lambda})^{n}$ gives a mixing bound of

$O(((2\hat{\lambda})^{6(t+1)})^{2}(\frac{\hat{\lambda}}{1+\hat{\lambda}})^{2}(1+\log\hat{\lambda})\cdot
n^{2\log(4\frac{1+\lambda}{\lambda}(8\hat{\lambda}^{2})^{t+2})/\log(6/5)+3})$
$=O(((2\hat{\lambda})^{12(t+1)})(\frac{\hat{\lambda}}{1+\hat{\lambda}})^{2}(1+\log\hat{\lambda})\cdot
n^{2(2+\log(\frac{1+\lambda}{\lambda})+(t+2)(3+\log\hat{\lambda}))/\log(6/5)+3}).$

###  H.4 Rapid mixing in the relaxed hierarchical framework for all
$\lambda>0$

We now generalize Lemma H.1 to all $\lambda>0$, finishing the proof of
Theorems 1.2 and 1.3.

######  Lemma H.10.

For the Glauber graphs $\mathcal{M}_{\textnormal{BEC}}(G)$ and
$\mathcal{M}_{\textnormal{DOM}}(G)$, with classes defined as in Lemma H.1, and
with stationary distribution $\pi$ induced by parameter $\lambda$ as in the
discussion in Section G.1, the flow construction in Lemma H.1 results in a
congestion factor gain of at most $\rho_{\max}=O(1)$ at each of the $O(\log
n)$ levels of induction, resulting in at most polynomial overall congestion.

######  Proof H.11.

We need to show that the flow construction within a class
$\mathcal{C}_{\textnormal{}}(T)$ in Lemma H.1 produces at most an
$O(1)$-factor increase in congestion; the rest of the argument is similar to
the proof of Lemma G.10. For the case of dominating sets, consider a pair of
$\mathcal{C}_{\textnormal{DOM}}(T_{W})\subseteq\mathcal{C}_{\textnormal{DOM}}(T)$
and
$\mathcal{C}_{\textnormal{DOM}}(T_{W^{\prime}})\subseteq\mathcal{C}_{\textnormal{DOM}}(T)$.
For every such pair, consider the intersection $\mathcal{I}$ of the two
subclasses, namely the set of dominating sets in which for every input graph
vertex $v\in W\cup W^{\prime}$, some neighbor of $v$ is selected in $A$, and
for every vertex $w\in U\setminus(W\cap W^{\prime})$, some neighbor of $w$ is
selected in $B$. There exists an $O(1)$-to-1 mapping from
$\mathcal{C}_{\textnormal{DOM}}(T_{W})$ to $\mathcal{I}$—found by adding
$O(1)$ neighbors of vertices in $U$ as described above to each dominating set
$S\in\mathcal{C}_{\textnormal{DOM}}(T_{W})$—under which the image $S^{\prime}$
of $S$ has $|S^{\prime}\setminus S|=O(1)$, and therefore
$\pi(S^{\prime})=\lambda^{|S^{\prime}\setminus S|}\pi(S)=\Theta(1)\pi(S)$.
This shows that
$\pi(\mathcal{I})=\Theta(\pi(\mathcal{C}_{\textnormal{DOM}}(T_{W})))=\Theta(\pi(\mathcal{C}_{\textnormal{DOM}}(T_{W^{\prime}})))$.

Thus we use the overlaps between classes to route flow along a path of classes
as in the proof of Lemma H.1. As before, at each class in the path, the
internal routing produces an $O(1)$ factor increase in the congestion within
the class. The concern, again, is that due to overlap, there may be edges
belonging to multiple classes that thus incur congestion multiple times in the
routing of the flow; as before, this is not a problem as there are $O(1)$
pairs of classes for which this occurs.

The argument for $\mathcal{M}_{\textnormal{BEC}}(G)$ is similar, with the
intersection $\mathcal{I}$ found by selecting sufficiently many edges incident
to each vertex $x\in X$ to satisfy membership in both subclasses
$\mathcal{C}_{\textnormal{BEC}}(T_{\beta})$ and
$\mathcal{C}_{\textnormal{BEC}}(T_{\beta^{\prime}})$.

###  H.5 Rapid mixing of the Glauber dynamics on $b$-matchings for all
$\lambda>0$

For the claim about $b$-matchings in Theorem 1.3, we do not need the relaxed
framework; in fact it suffices to combine Lemma E.5 with the following lemma:

######  Lemma H.12.

It is easy to adapt the proof of Lemma G.10 to the hierarchical framework,
proving the claim about the Glauber dynamics on $b$-matchings in Theorem 1.3
for all $\lambda>0$.

######  Proof H.13.

The proof of Lemma G.10 uses a simple mapping argument to show that for every
ancestor $\mathcal{C}_{\textnormal{}}(T_{i})$ of a class
$\mathcal{C}_{\textnormal{}}(T)$,
$\pi(\mathcal{C}_{\textnormal{}}(T_{i}))=\Theta(1)\pi(\mathcal{C}_{\textnormal{}}(T))$,
then allows each boundary edge $e$ between classes to carry $O(1)Q(e)$ units
of flow across the boundary, by ensuring that each boundary vertex $S$ carries
flow in proportion to its weight $\pi(S)$. Since all pairs of classes
$\mathcal{C}_{\textnormal{}}(T),\mathcal{C}_{\textnormal{}}(T^{\prime})$ have
a common ancestor in the case of $b$-matchings, we in fact have
$\pi(\mathcal{C}_{\textnormal{}}(T))=\Theta(1)\pi(\mathcal{C}_{\textnormal{}}(T^{\prime}))$
for every pair of classes
$\mathcal{C}_{\textnormal{}}(T),\mathcal{C}_{\textnormal{}}(T^{\prime})$. The
bound on flow across the boundary therefore still holds; the argument for
bounding congeston factor increase wthin a class is the same as in the proof
of Lemma G.10.

For the specific mixing upper bound for $b$-matchings, we use Lemma D.3, and
observe that $K\leq 2^{\Delta(t+1)}$; the parameter $\lambda$ contributes at
most a $\hat{\lambda}^{\Delta(t+1)}$ factor,
$1/\pi_{\min}^{*}\leq(2\hat{\lambda})^{m}$, and $\Delta_{\mathcal{M}}\leq m$,
so we have a mixing upper bound of

$O(((1+\hat{\lambda})\hat{\lambda})^{2}(2((2\hat{\lambda})^{\Delta(t+1)}+1))^{2\log
n}m^{3}(1+\log\hat{\lambda}))$
$=O(((1+\hat{\lambda})\hat{\lambda})^{2}(1+\log\hat{\lambda})m^{3}n^{2\Delta(t+2)(1+\log\hat{\lambda})+2}).$

###  H.6 Maximal independent sets and maximal $b$-matchings in the non-
hierarchical framework

####  H.6.1 Dealing with internally disconnected classes

As noted in Appendix H, we use the non-hierarchical framework and assume
bounded treewidth and degree for the chains on maximal independent sets and
maximal $b$-matchings. Once we have defined these chains, we will see that
partitioning the Glauber graph for each chain in the natural way will result
in classes that are not necessarily internally connected. The solution will be
to relax the framework conditions so that the classes need not be disjoint—but
then require that every pair of overlapping classes must overlap in a large
number of vertices. More precisely:

######  Lemma H.14.

Suppose a Glauber graph $\mathcal{M}_{\textnormal{}}(G)$ satisfies the
conditions of the non-hierarchical framework in Section 3.3, except that:

  1. 1.

The $O(1)$ classes are not necessarily disjoint.

  2. 2.

Each pair of classes $\mathcal{C}_{\textnormal{}}(T)$ and
$\mathcal{C}_{\textnormal{}}(T^{\prime})$ sharing at least one vertex shares
$\Theta(1)|\mathcal{C}_{\textnormal{}}(T)|=\Theta(1)|\mathcal{C}_{\textnormal{}}(T^{\prime})|$
vertices.

Then the expansion of $\mathcal{M}_{\textnormal{}}(G)$ is $\Omega(1/n^{c})$,
where $c=O(1)$.

######  Proof H.15.

The multicommodity flow construction is as in the proof of Lemma 3.7, except
that when sending flow from $S\in\mathcal{C}_{\textnormal{}}(T)$ to
$S^{\prime}\in\mathcal{C}_{\textnormal{}}(T^{\prime})\neq\mathcal{C}_{\textnormal{}}(T)$
via a path through intermediate classes, we now have some pairs of
intermediate classes that share boundary vertices, instead of sharing boundary
edges. The flow is the same as before, except that there is no need to send
flow across a boundary in these cases.

The congestion analysis is the same as in the proof of Lemma H.1.

####  H.6.2 Maximal independent sets

Figure 4: Two maximal independent sets in a graph $G$: $S$ (left) and
$S^{\prime}$ (right). $S$ and $S^{\prime}$ differ by a move, with the
separator $X$ inducing the classes to which the sets belong. $S^{\prime}$
results from adding $v$ to $S$, removing the neighbors of $v$, and adding some
of the neighbors of the removed vertices.