Random Graph G(n,d/n) average degree:d max-degree:whp q-colorable whp for a g=O(d/In d) rapid mixing of(block)Glauber dynamics: [Dyer,Flaxman,Frieze,Vigoda 06]g=O(Inln n/Inlnln n) [Efthymiou,Spirakis 07][Mossel,Sly 08]g=poly(d) [Efthymiou 14]g >5.5d+1 spatial mixing?
Random Graph G(n,d/n) • [Dyer, Flaxman, Frieze, Vigoda 06] q=O(lnln n/lnlnln n) • [Efthymiou, Spirakis 07] [Mossel, Sly 08] q=poly(d) • [Efthymiou 14] q >5.5d+1 average degree: d max-degree: ⇥ ✓ ln n ln ln n ◆ whp rapid mixing of (block) Glauber dynamics: q-colorable whp for a q=O(d/ln d) spatial mixing?
Negative Result for SSM strong spatial mixing(SSM): for any vertex v Pr[c(v)=x|o△，oA]≈Pr[C(v)=x|T△，OA] in G(n,dln) for any g=O(1) q colors:▣▣▣▣☐ whp,3:(In n)long 个不个不 This counter-example only affect the strong spatial mixing
Negative Result for SSM R G v t ⇤ strong spatial mixing (SSM): for any q=O(1) q colors: whp, ∃: Ω(ln n) long v u o q-2 { } { } { } { } in G(n, d/n) for any vertex v ∆ Pr[c(v) = x | , ⇤] ⇡ Pr[c(v) = x | ⌧, ⇤] This counter-example only affect the strong spatial mixing