## A Tutorial on Various Aspects of Mixing

Prasad Tetali

School of Mathematics & School of Computer Science Georgia Institute of Technology

January 9, 2009

1/42

Acknowledgement

The part Colorings on Trees of this presentation was given to me by Juan Vera. The part on Broadcasting on a Tree was given by Nayantara Bhatnagar. I am grateful for their help.

Prasad Tetali

## Catalan Shuffling: an open question

Consider the setC_{n} of triangulations of a convexn-sided
polygon, for integern≥4.

Well-known: |C_{n}|= [1/(n+ 1)] ^{2n}_{n}

, thenth Catalan number.

I A shuffle consists of picking one of then−3 diagonals uniformly at random and “flipping the diagonal”–

removing the diagonal and in the quadrilateral created by this removal, placing the (only possible) other diagonal.

I How long until the triangulation is random?

I Conjecture (Aldous). O(n^{3/2}) shuffles ought to be enough!,

I Best known. Lower bound : Ω(n^{3/2}) (Mol-Ree-Ste ’99)
Upper bound ofO(n^{4}(logn)) (McS–T. ’99).

3/42

## Catalan Shuffling: an open question

Consider the setC_{n} of triangulations of a convexn-sided
polygon, for integern≥4.

Well-known: |C_{n}|= [1/(n+ 1)] ^{2n}_{n}

, thenth Catalan number.

I A shuffle consists of picking one of then−3 diagonals uniformly at random and “flipping the diagonal”–

removing the diagonal and in the quadrilateral created by this removal, placing the (only possible) other diagonal.

I How long until the triangulation is random?

I Conjecture (Aldous). O(n^{3/2}) shuffles ought to be enough!,

I Best known. Lower bound : Ω(n^{3/2}) (Mol-Ree-Ste ’99)
Upper bound ofO(n^{4}(logn)) (McS–T. ’99).

## Catalan Shuffling: an open question

Consider the setC_{n} of triangulations of a convexn-sided
polygon, for integern≥4.

Well-known: |C_{n}|= [1/(n+ 1)] ^{2n}_{n}

, thenth Catalan number.

I A shuffle consists of picking one of then−3 diagonals uniformly at random and “flipping the diagonal”–

removing the diagonal and in the quadrilateral created by this removal, placing the (only possible) other diagonal.

I How long until the triangulation israndom?

I Conjecture (Aldous). O(n^{3/2}) shuffles ought to be enough!,

I Best known. Lower bound : Ω(n^{3/2}) (Mol-Ree-Ste ’99)
Upper bound ofO(n^{4}(logn)) (McS–T. ’99).

3/42

## Catalan Shuffling: an open question

Consider the setC_{n} of triangulations of a convexn-sided
polygon, for integern≥4.

Well-known: |C_{n}|= [1/(n+ 1)] ^{2n}_{n}

, thenth Catalan number.

I How long until the triangulation israndom?

I Conjecture(Aldous). O(n^{3/2}) shuffles ought to be enough!,

^{3/2}) (Mol-Ree-Ste ’99)
Upper bound ofO(n^{4}(logn)) (McS–T. ’99).

## Catalan Shuffling: an open question

Consider the setC_{n} of triangulations of a convexn-sided
polygon, for integern≥4.

Well-known: |C_{n}|= [1/(n+ 1)] ^{2n}_{n}

, thenth Catalan number.

I How long until the triangulation israndom?

I Conjecture(Aldous). O(n^{3/2}) shuffles ought to be enough!,

^{3/2}) (Mol-Ree-Ste ’99)
Upper bound ofO(n^{4}(logn)) (McS–T. ’99).

3/42

## The rho (nonreversible) walk – recently settled question

Consider thesimple random walkon the discrete circle Z_{p} (for
p: prime) – move fromatoa±1, with equal probability.

Well-known: O(n^{2}) steps to get to a randomi∈ {0,1, . . . , p}.

I Add a doublingmove – from atoa±1 or 2a, with probability 1/3 independently.

I Now how long until random?

Theorem(Kim-Mon–T. ’07). O(logn log logn) moves sufficient. Motivation: Arises in the analysis of Pollard’s Rho algorithm for finding thediscrete logarithm in a cyclic group of prime order.

## The rho (nonreversible) walk – recently settled question

Consider thesimple random walkon the discrete circle Z_{p} (for
p: prime) – move fromatoa±1, with equal probability.

Well-known: O(n^{2}) steps to get to a randomi∈ {0,1, . . . , p}.

I Add a doublingmove – from atoa±1 or 2a, with probability 1/3 independently.

I Now how long until random?

Theorem(Kim-Mon–T. ’07). O(logn log logn) moves sufficient. Motivation: Arises in the analysis of Pollard’s Rho algorithm for finding thediscrete logarithm in a cyclic group of prime order.

4/42

## The rho (nonreversible) walk – recently settled question

Consider thesimple random walkon the discrete circle Z_{p} (for
p: prime) – move fromatoa±1, with equal probability.

Well-known: O(n^{2}) steps to get to a randomi∈ {0,1, . . . , p}.

I Add a doublingmove – from atoa±1 or 2a, with probability 1/3 independently.

I Now how long until random?

Theorem(Kim-Mon–T. ’07). O(logn log logn) moves sufficient. Motivation: Arises in the analysis of Pollard’s Rho algorithm for finding thediscrete logarithm in a cyclic group of prime order.

## The rho (nonreversible) walk – recently settled question

_{p} (for
p: prime) – move fromatoa±1, with equal probability.

Well-known: O(n^{2}) steps to get to a randomi∈ {0,1, . . . , p}.

I Add a doublingmove – from atoa±1 or 2a, with probability 1/3 independently.

I Now how long until random?

Theorem(Kim-Mon–T. ’07). O(logn log logn) moves sufficient.

Motivation: Arises in the analysis of Pollard’s Rho algorithm for finding thediscrete logarithm in a cyclic group of prime order.

4/42

## The rho (nonreversible) walk – recently settled question

_{p} (for
p: prime) – move fromatoa±1, with equal probability.

Well-known: O(n^{2}) steps to get to a randomi∈ {0,1, . . . , p}.

I Add a doublingmove – from atoa±1 or 2a, with probability 1/3 independently.

I Now how long until random?

Theorem(Kim-Mon–T. ’07). O(logn log logn) moves sufficient.

Motivation: Arises in the analysis of Pollard’s Rho algorithm for finding thediscrete logarithm in a cyclic group of prime order.

## Welcome to Markov Chains

Let (Ω, P, π) : denote a Markov chain on state space Ω, with the transition probab. matrixP, and (unique) invariant measureπ:

P(x, y)≥0,∀x, y∈Ω and X

y

P(x, y) = 1,∀x∈Ω,

X

x∈Ω

π(x)P(x, y) =π(y), ∀y∈Ω.

I Always assumeirreducible, withπ having full support on Ω.

I Typically assume aperiodic, soP^{n}(x,·)→π(·), as n→ ∞.

I Often have reversibility :

π(x)P(x, y) =π(y)P(y, x), ∀x, y∈Ω.

5/42

Markov Chain Monte Carlo

Typically given a LARGE set Ω, the goal is to sample elements from Ω at random from a desired distributionπ over Ω.

Usuallyπ is given implicitly.

Examples: weighted matchings, uniform independent sets, colorings etc. of a given graph.

The MCMC approach to sampling is to construct a Markov chain (based on “local” moves) on Ω which converges toπ.

I Start at any x0 ∈Ω; run the chain for T steps,
and output x_{T}.

I key question: How large doesT have to be so that the
distribution of x_{T} is a good approximation toπ?

## Some Successes

Defn. Fully poly. randomized approx. scheme(FPRAS): Given inputx, error parameter >0, and a confidence parameter δ >0, an approximation algorithm outputting A(x) (for the true valuef(x)), so that

Pr

(1−)f(x)≤A(x)≤(1 +)f(x)

≥1−δ ,
in time polynomial in|x|,^{−1} and log(1/δ).

Some examples having an FPRAS using the MCMC approach:

I Counting Matchings in General Graphs, Perfect Matchings in Bipartite Graphs, Computing the permanent of a matrix

I Counting the number of linear extensions of a poset

I Computing the volume of an n-dim. convex body

7/42

## Some Frustrations

Some notorious open problems:

I Generating perfectmatchings u.a.r. from a general G.

I Generating acyclic orientations of Gu.a.r. from a given undirected graph G

I Contingency Table Problems: given row and column sums, generate u.a.r. a table of nonneg. integers with those sums

I Is the basis-exchange walk on bases of an arbitrary matroid rapidly mixing? (known for spanning trees, and balanced matroids [F-M ’9?])

I Generating independent sets from a given bipartitegraph

## Many Paths to Mixing – Distance to Equilibrium

Letk_{n}^{x}(y) =P^{n}(x, y)/π(y) density w.r.t. π at time n≥0, so
under aperiodicity,k^{x}_{n}(y)→1.

Defn. L^{p}-distance:

kk_{n}−1k^{p}_{p,π} =P

y∈Ω|k_{n}(y)−1|^{p}π(y), 1≤p <+∞.

Forµ: probab. distribution on Ω,

I p= 1:

kµ−πk_{tv}= 1
2

X

y

|µ(y)−π(y)|= 1

2kµ/π−1k_{1,π},

I p= 2:

Var_{π}(µ/π) =X

y

µ(y) π(y)−1

2

π(y) =kµ/π−1k^{2}_{2,π}.
Defn. Rel. Entropy:

D(P^{n}(x,·)kπ) =P

yP^{n}(x, y) logP^{n}(x, y)/π(y)= Ent_{π}(k_{n}^{x}),
where Entπ(f) = Eπflogf−Eπflog(Eπf).

9/42

Various Mixing Times

A Key Question. Howquicklydoes it converge to 1?

The total variation, relative entropy andL^{2} mixing times are
defined as follows, (using worst-case starting point).

τ() = min{n:∀x∈Ω, kP^{n}(x,·)−πk_{tv}≤}
τ_{D}() = min{n:∀x∈Ω, D(P^{n}(x,·)kπ)≤}
τ2() = min{n:∀x∈Ω, kk^{n}(x,·)−1k_{2,π}≤}

I

## List of Techniques

Functional Analytic,IsoperimetricApproaches:

I Spectral Gap,Conductance (Cheeger-type constants)

I Entropy Constant (Dai Pra-Paganoni-Posta, Gao-Quastel, Bobkov-T.), Log-Sobolev Constant (Gross, Bakry-Emery, Diaconis-Saloff-Coste, Miclo, ...)

I Spectral Profile (Goel-Montenegro-T.) and Isoperimetric Profile(Kannan-Lovasz) ProbabilisticApproaches:

I Coupling, Path coupling (Bubley-Dyer),

Coupling From the Past (Propp-Wilson), Evolving Sets (Morris-Peres)

Other Techniques

I Decomposition and Comparison

11/42

## Treatment with Dirichlet Forms

The following will be done on the white board:

I Motivating definitions of spectral gap, entropy constant, ...

I Comparison of Dirichlet Forms

An Amazing Conjecture

[Due to Aldous-Diaconis ’92].

Conjecture. For everyG,λ_{IP}(G) =λ_{RW}(G).

IP: Start withnlabeled particles on ann-vertex graph. For each edgeij independently and at rate 1, interchangethe particlesiand j. (This is reversible w.r.t. uniform distribution onn! configurations. of particles.)

RW: Observe a single particle above, thus obtaining a (continuous) time simple random walk onG.

I Known to hold for G=Cn, Kn, Trees, and a bit more ...

I Asymptotically forG:d-dimensional grid of side length n.

13/42

## The logarithmic factor: some examples

I Entropy Constant vs Log-Sobolev constant:

random transpositions, k-sets of an n-set

I The Pollard Rho walk

I The Thorp shuffle

Coupling

Colorings on graphs : a case study

Refer to the file coloring.pdf, which covers Jerrum’s coupling and a bit more.

15/42

## Next Topic

Temporal vs SpatialMixing

Temporal Mixing and Uniqueness of Gibbs

Typically one expects fast mixing of Glauber (and other local) dynamics in the uniqueness regime, and (exponentially) slow mixing in the non-uniqueness regime:

Examples include: OnZ^{d},

Ising at low-temperature (largeβ >0), Hard-core lattice gas (i.e., weighted independent sets), etc.

However, Glauber dynamics onZ^{d}in the multiphase region is
still poorly understood: F. Martinelli’s problem with the
+boundary condition onZ^{2}.

17/42

## An Amazing Theorem

[Martinelli-Olivieri-Schonman’94].

For the Ising model on a finite box of sizeninZ^{2}, the Glauber
dynamics satisfies:

I If T > Tc, then mixing time =O(nlogn)

I If T < Tc, then mixing time = exp(Ω(√ n)).

A notion of Strong Spatial Mixing

Defn. A system hasSSMif∃ constantsβ and α >0, such that
for any two subsets Λ,Ψ, with Λ⊂Ψ, any site u∈∂Ψ, and any
pair of bdry configs. τ andτ^{u} differing only atu,

d µ^{τ}_{Ψ}, µ^{τ}_{Ψ}^{u}

|_{Λ}≤β|Λ|exp(−α dist(u,Λ)).

I Weak Spatial Mixing: replaced(u,Λ) by d(∂Ψ,Λ); holds up to (and corresponds to) uniqueness of Gibbs etc.

19/42

## Optimal Temporal Mixing

[In words: Glauber dynamics on a finite volume Ψwith ANY bdry config. reaches stationarity in timeO(nlogn), n=|Ψ|.]

Defn. Glauber has OTM if∃ const. b, c >0 such that

∀Ψ⊂⊂ Z^{d} with any bdry config. for any two instances (Xt)
and (Y_{t}) of the chain, anyk∈ Z^{+},

d(X_{kn}, Y_{kn})≤bn e^{−ck}.

I e.g., if entropy constantρ0≥c^{0}/n, then OTM holds.

Thm. [Stroock-Zegarlinski’92]. For spin systems onZ^{d}, with
nearest neighbor interactinos, OTM holds iff SSM holds.

## Path of Disagreement in Bdd-degree Graphs

Key Lemma[Zegarlinski’ ??, van den Berg’93] (DSVW’02):

G= (V, E), |V|=n, max degree ∆.

LetA, B⊂V arbitrary with r= dist(A, B).

Xt, Yt : two copies of Glauber on GwithX0≡Y0 off ofA.

Then for pos. integerk≤r/[(∆−1)e^{2}], if we run for T =kn
steps, we have

P(X_{T}(B)6=Y_{t}(B))≤4 min{|A|,|B|}(∆−1)ek
r

r

. The probability is under “identity coupling” of (Xt),(Yt).

I Cor. IfT =kn,r= dist(A, B)≥(∆−1)e^{2}k,
P(XT(b)6=YT(B))≤4|A|e^{−dist(A,B)}.
WMA assumed above that|A| ≤ |B|.

21/42

## OTM implies SSM in Z

^{d}

Run chain (X_{t}) with the stat. measureµ^{τ}_{Ψ}, and chain (Y_{t}) with
the stat. measureµ^{τ}_{Ψ}^{u}, starting withX_{0}=Y_{0} (in the same
configuration of spins).

Stop at timet= _{(2d−1)e}^{dist(u,Λ)}2 n(say). Then

I

d(µ^{τ}_{Ψ}, µ^{τ}_{Ψ}^{u})≤d(µ^{τ}_{Ψ}, Xt) +d(Xt, Yt) +d(µ^{τ}_{Ψ}^{u}, Yt).

I

d(Xt, Yt)|_{Λ}≤4|Λ|e^{−dist(u,Λ)},
sincedisagreement has not percolated!

I OTOH,

d(µ^{τ}_{Ψ}, X_{t})|_{Λ}≤b^{0}|Λ|exp

− c^{0}

(2d−1)e^{2} dist(u,Λ)
,
due to OTM.

OTM implies SSM in Z

^{d}

Run chain (X_{t}) with the stat. measureµ^{τ}_{Ψ}, and chain (Y_{t}) with
the stat. measureµ^{τ}_{Ψ}^{u}, starting withX_{0}=Y_{0} (in the same
configuration of spins).

Stop at timet= _{(2d−1)e}^{dist(u,Λ)}2 n(say). Then

I

d(µ^{τ}_{Ψ}, µ^{τ}_{Ψ}^{u})≤d(µ^{τ}_{Ψ}, Xt) +d(Xt, Yt) +d(µ^{τ}_{Ψ}^{u}, Yt).

I

d(Xt, Yt)|_{Λ}≤4|Λ|e^{−dist(u,Λ)},
sincedisagreement has not percolated!

I OTOH,

d(µ^{τ}_{Ψ}, X_{t})|_{Λ}≤b^{0}|Λ|exp

− c^{0}

(2d−1)e^{2} dist(u,Λ)
,
due to OTM.

22/42

## OTM implies SSM in Z

^{d}

Run chain (X_{t}) with the stat. measureµ^{τ}_{Ψ}, and chain (Y_{t}) with
the stat. measureµ^{τ}_{Ψ}^{u}, starting withX_{0}=Y_{0} (in the same
configuration of spins).

Stop at timet= _{(2d−1)e}^{dist(u,Λ)}2 n(say). Then

I

d(µ^{τ}_{Ψ}, µ^{τ}_{Ψ}^{u})≤d(µ^{τ}_{Ψ}, Xt) +d(Xt, Yt) +d(µ^{τ}_{Ψ}^{u}, Yt).

I

d(Xt, Yt)|_{Λ}≤4|Λ|e^{−dist(u,Λ)},
sincedisagreement has not percolated!

I OTOH,

d(µ^{τ}_{Ψ}, Xt)|_{Λ}≤b^{0}|Λ|exp

− c^{0}

(2d−1)e^{2} dist(u,Λ)

, due to OTM.

Proof Sketch of Key Lemma

Observe: if sitev at timeT has different spins, then there must exist a path of disagreement fromA tov: i.e., ∃ path

v0, v1, . . . , vl=v and 0< t1 < t2· · ·< tl≤T, s.t. v0 ∈A, and
v_{i} updated at timet_{i}.

I Pr[v_{0}, . . . , v_{l}]≤ ^{T}_{l}

(1/n)^{l},for a fixed path.

I No. of paths of lengthl≥r fromA toB is at most
min{|A|,|B|}∆(∆−1)^{l−1}.

I So Pr(X_{kn}(B)6=Y_{kn}(B))≤ |A|

∆ (∆−1)

P

l≥r

_{(∆−1)ek}

l

l

≤4|A|_{(∆−1)ek}

r

r

,

≤4|A|e^{−r}, ifr ≥(∆−1)e^{2}k.

23/42

## But ... what about the sub-exponential growth?

Have we used the fact that we were inZ^{d}?

I In the OTM bound, we really should have used a bound of
d(µ^{τ}_{Ψ}, Xt)|_{Λ}≤b^{0}|Ψ|exp

− c^{0}

(2d−1)e^{2} dist(u,Λ)
,
rather than the smaller bound with |Λ|in place of|Ψ|,
since the chain was run on Ψ rather than on Λ.

I So to justify the “fudge” we actually need an extra lemma:

this would argue that we could first restrict our attention
to dynamics inside a volume Λ^{k} which contains all sites
within distance ˆk= (2d−1)e^{2}k from some site in Λ.

I The choice of ˆk still lets us use the path of diagreement argument on not reachingΛ.

## Fudge contd...

I The above would then give a bound of |Λ^{k}|e^{−c}

0dist(u,Λ) (2d−1)e2

(plus another exponential term such as, e^{−ck|Λ}^{k}^{|}, for the
probability of missing Λ^{k}, while choosing sites at random
from Ψ: using Chernoff’s bound, e.g.)

I Now crucially, the “sub-exponential growth” of Z^{d} can be
used in saying |Λ^{k}| ≤

2[2d−1]e^{2}kd

|Λ|and absorbing it into :

|Λ^{k}|e^{−c}^{0}^{···}≤ |Λ|e^{−c}

00 dist(u,Λ) (2d−1)e2 .

Details in [Dyer-Sinclair-Vigoda-Weitz’02].

25/42

## Spectral Gap and Correlations on a general graph

At∞ temperature, where distinct vertices are independent, the Glauber dynamics on a graph ofnvertices reduces to an

(accelerated by a factor ofn) random walk on a discrete n-cube where the relaxation is Θ(1).

The next result shows that at any temperature where such fast relaxation takes place, a fairly strong form of independence holds. The setting is that of any graph ofbounded degree.

Spectral Gap and Correlations – 2

Thm. [Ber-Ken-Mos-Per’05] LetGbe bdd. degree graph, and
letσ_{r} be config. on the setG_{r} of all vertices at distance r from
a fixed vertexv. Let therelaxation timeof Glauber dynamics
onGr satisfyτ2(Gr) =O(1). Then the Gibbs distribution on
G_{r} has the following property:

For any fixed setA of vertices,∃c_{A}>0, s.t. for r large enough,
Cov[f, g]≤e^{−c}^{A}^{r}p

Var(f)Var(g),

providedf(σ) depends only onσA andg(σ) depends only onσr.
(Equivalently,∃c^{0}_{A}>0 s.t. the mut. inform. I(σ_{A}, σ_{r})≤e^{−c}^{0}^{A}^{r}.)

I Proof uses disagreement percolation and coupling as before.

I Thm could hold also when there are multiple Gibbs measures– e.g., the Ising model in the “intermediate regime” – for 1−2≤1/√

b, one gets limr→∞I[σ_{0}, σ_{r}] = 0.

27/42

## An Open Question

Question[BKMP’05]:

For the Ising model (with free boundary conditions and no external field) on a general graph of bounded degree, does the converse of the above theoremhold?

That is, does uniform exponential decay of point-to-set correlations imply a uniform spectral gap?

I F.M. : Not always true – fails in certain lattices if plus bdry conditions are allowed.

## Broadcast Process on a Tree

Model

I T infinite rooted tree where each node has ∆ children.

I k colors,σv ∈[k] is the color at vertexv.

I Choose σ_{r} at the root uniformly at random.

I Broadcast process.

I Independent Markov chain on each edge (u, v). P(i, j) = P[σu=j|σv=i]

I Proper colorings.

P(i, j) = δ_{i6=j}
k−1

29/42

Broadcast Process on a Tree

Model

I T infinite rooted tree where each node has ∆ children.

I k colors,σv ∈[k] is the color at vertexv.

I Choose σ_{r} at the root uniformly at random.

I Broadcast process.

I Independent Markov chain on each edge (u, v).

P(i, j) = P[σu=j|σv=i]

I Proper colorings.

P(i, j) = δ_{i6=j}
k−1

## Broadcast Process

30/42

Broadcast Process

Broadcast Process

32/42

Broadcast Process

Broadcast Process

34/42

Broadcast Process

Broadcast Process

36/42

Reconstruction

How doesµ(·|X) behave as a function of a typical coloringX?

∃c, lim

`→∞E_{X}(|µ(c|X)− 1
k|)>0

Applications I -Phylogeny

I [Mossel ’04], [Daskalakis-Mossel-Roch ’06 ] Evolution of DNA, phylogenetic reconstruction.

38/42

Applications II - Convergence of Markov Chains

I [Kenyon-Mossel-Peres ’01], [Berger-K-M-P ’05]

O(n) relaxation time for Glauber dynamics on bounded degree graphs implies non-reconstruction.

I [Martinelli-Sinclair-Weitz ’03] Exponential decay of correlation on the tree impliesO(nlnn) convergence for Glauber dynamics when “uniqueness” holds.

## Applications III - Replica Symmetry Breaking Transition

I [Achlioptas, Coja-Oghlan ’08]

(1/2 +o(1))∆/ln ∆< k_{d}<(1−o(1))∆/ln ∆.

I Conjecture that k_{d} is the same as the reconstruction
threshold for trees. There is very recent work in this
direction by [Montanari-Restrepo-T.]

40/42

Bounds on the Threshold for Non-reconstruction

I [Brightwell-Winkler’00]

Non-Reconstruction fork≥∆ + 1

I [Jonasson’02]

fork≥∆ + 1: root is unbiased for any fixed coloringof the leaves; (thus the Gibbs measure is unique.)

I [Mossel-Peres ’03]

Reconstruction when k≤ ^{(1−ε)∆}_{ln ∆} .

I [B-Vera-Vigoda-Weitz ’08]

Non-reconstruction for k > ^{(1+ε)∆}_{ln ∆} for ∆≥∆ε.

I [Sly ’08]

Non-reconstruction for ∆≤k(lnk+ ln lnk+ 1 +o(1)).

Reconstruction for ∆≥k(lnk+ ln lnk+ 1−ln 2−o(1)).

## Bounds on Mixing

I [Bhatnagar-Vera-Vigoda-Weitz ’08]

O(nlogn) mixing for a certain Block dynamics, by
bounding the entropy constant of the dynamics for
k > ^{(1+ε)∆}_{ln ∆} for ∆≥∆ε.

I [Goldberg-Jerrum-Karpinsky ’08]

Glauber: For fixed kand ∆ so that 3≤k≤∆/2 log(∆):

Upper bound ofn^{O(∆/}^{log ∆)} and a lower bound of
n^{Ω(∆/k}^{log ∆)}.

Problem 1. More precise bounds on the performance of Glauber “around”k= ∆/log ∆ ,especially in the range

∆/2 log ∆< k <2∆/log ∆ . Problem 2. SSM for k≥∆ + 1.

42/42