at each step: ·randomly pick a vertex veV and a color c∈[q]; change the color of v to c if it is proper; X,Y disagree at vo 01 coupling (X,Y(X',Y): E0X,y1xy-n=m+D++(+） n q =1-g-2d(o) ≤1、9-24 nq nq q≥2A+1> Tmix =O(gnlogn)
• randomly pick a vertex v∊V and a color c∊[q]; • change the color of v to c if it is proper; at each step: v0 v0 coupling (X,Y)→(X’,Y’): X,Y disagree at v0 : q 2 + 1 ⌧mix = O(qn log n) E[d(X0 , Y 0 ) | X, Y ] = n (d(v0) + 1) n + 1 n d(v0) q + d(v0) n ✓ 1 + 1 q ◆ = 1 q 2d(v0) nq 1 q 2 nq
Path Coupling (Bubley-Dyer 1997): there is a coupling (X,)(X',Y)such that V proper colorings x,ye[g]y that disagree at 1 vertex Eld(X',Y)X=x,Y=y]<(1-a)d(x,y) for some a∈[0,1] > Tmix=O(log n)
∀ proper colorings x,y∈[q]V there is a coupling (X,Y)→(X’,Y’) such that for some α∈[0,1] ⌧mix = O 1 ↵ log n Path Coupling (Bubley-Dyer 1997): that disagree at 1 vertex E[d(X0 , Y 0 ) | X = x, Y = y] (1 ↵)d(x, y)
there is a coupling (X,Y(X',Y)such that V proper colorings x,ye[g]y that disagree at 1 vertex Eld(X',YX=x,Y=y<(1-a)d(x,y) for some a∈[0,1] there is a coupling (,Y->(,Y)such that V proper colorings x,ye[g]v Eld(X',Y)X=x,Y=y<(1-a)d(x,y) for some a∈[0,1] >Tmix=0(3logn）
∀ proper colorings x,y∈[q]V there is a coupling (X,Y)→(X’,Y’) such that for some α∈[0,1] ⌧mix = O 1 ↵ log n ∀ proper colorings x,y∈[q]V there is a coupling (X,Y)→(X’,Y’) such that for some α∈[0,1] E[d(X0 , Y 0 ) | X = x, Y = y] (1 ↵) d(x, y) that disagree at 1 vertex E[d(X0 , Y 0 ) | X = x, Y = y] (1 ↵)d(x, y)
Mixing Why should a uniform random walk on a graph be rapidly mixing? Why should a Markov chain be rapidly mixing? initial distribution g the decreasing rate of gpe-
Mixing • Why should a uniform random walk on a graph be rapidly mixing? • Why should a Markov chain be rapidly mixing? kqPt ⇡k1 initial distribution q the decreasing rate of
Spectral Decomposition Spectral Theorem P:symmetric nxn matrix eigenvalues:d≥2≥.≥λn the corresponding eigenvectors v1,v2,...,v are orthonormal m g∈Rm q=>civi where ci=qTvi i=1 qP=∑cP=∑c入 2=1 i=1
Spectral Decomposition P : eigenvalues : symmetric n×n matrix the corresponding eigenvectors v1, v2, ..., vn are orthonormal 1 2 ··· n Spectral Theorem where ci = qT vi = X n i=1 ciivi q = X n i=1 8q 2 R civi n qP = X n i=1 civiP