Spatial Mixing undirected G(V,E) 口 max-degree: q colors: d ▣ Gibbs measure:uniform random proper q-coloring of G c:V→[g region RCV △D∂R proper q-colorings,TA:△→[gl Pr[c(w)=x|o△]≈Pr[c(v)=x|T△] error exp (-t)Spatial Mixing undirected G(V,E) q colors: Gibbs measure: uniform random proper q-coloring of G c : V ! [q] R G v t region R ⇢ V proper q-colorings error < exp (-t) max-degree: d ∆ ￾￾, ⌧￾ : ￾ ! [q] ￾ ◆ @R Pr[c(v) = x | ￾￾] ⇡ Pr[c(v) = x | ⌧￾]