Spatial Mixing of Coloring Random Graphs Yitong Yin Nanjing University
Spatial Mixing of Coloring Random Graphs Yitong Yin Nanjing University
Colorings undirected G(V,E) max-degree: q colors: d 口 temporal mixing of approximately counting Glauber dynamics or sampling almost uniform 0:2→11/6 proper q-colorings of G [Jerrum'95] [Vigoda'99] [Salas-Sokal'97] [Bubley-Dyer'97] when q≥cd+B spatial mixing of conjecture:x=1 Gibbs measure
Colorings undirected G(V,E) approximately counting or sampling almost uniform proper q-colorings of G max-degree: q colors: d when q ≥αd+ temporal mixing of Glauber dynamics β spatial mixing of Gibbs measure ? α: 2 → 11/6 [Jerrum’95] [Salas-Sokal’97] [Bubley-Dyer’97] [Vigoda’99] conjecture: α=1
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 | ⌧]
Spatial Mixing weak spatial mixing (WSM): Pr[c(w)=x|o△]≈Pr[C(v)=x|TA] strong spatial mixing (SSM): Pr[c(v)=A,]Pr[c(v)=xTA,OA] error exp (-t) SSM:the value of critical to Pr[c(v)=O] counting and sampling is approximable by local information
Spatial Mixing R G v t ⇤ weak spatial mixing (WSM): strong spatial mixing (SSM): error < exp (-t) Pr[c(v) = x | ⇤] is approximable by local information SSM: the value of critical to counting and sampling Pr[c(v) = x | ] ⇡ Pr[c(v) = x | ⌧] Pr[c(v) = x | , ⇤] ⇡ Pr[c(v) = x | ⌧, ⇤] ∆
Spatial Mixing of Coloring q-coloring of G q≥0d+O(1) max-degree:d SSM:>1.763.. (solution to x=e) average degree? [Goldberg,Martin,Paterson 05]triangle-free amenable graphs [Ge,Stefankovic 11]regular tree [Gamarnik,Katz,Misra 12]triangle-free graphs Spatial-mixing-based FPTAS: ● [Gamarnik,Katz 07]>2.8432...,triangle-free graphs [Lu,Y.14]0>2.58071.. SSM→algorithm [Goldberg,Martin,Paterson 05]amenable graph,SSM=FPRAS [Y.,Zhang 13]planar graph (apex-minor-free),SSM=FPTAS
Spatial Mixing of Coloring • [Goldberg, Martin, Paterson 05] triangle-free amenable graphs • [Ge, Stefankovic 11] regular tree • [Gamarnik, Katz, Misra 12] triangle-free graphs q-coloring of G q ≥αd+O(1) max-degree: d • [Goldberg, Martin, Paterson 05] amenable graph, SSM 㱺 FPRAS • [Y., Zhang 13] planar graph (apex-minor-free), SSM 㱺 FPTAS • [Gamarnik, Katz 07] α>2.8432..., triangle-free graphs • [Lu, Y. 14] α>2.58071... SSM: α>1.763... xx (solution to ) = e SSM 㱺 algorithm Spatial-mixing-based FPTAS: average degree?