58 min
Seminar, Hosted by Simons Institute for the Theory of Computing
Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications
Massachusetts Institute of Technology
Recording
Abstract
Correlation decay for graph colourings is central to efficient sampling but remains difficult to prove near conjectured thresholds. This talk establishes strong spatial mixing on trees of maximum degree Delta for at least Delta plus three colours, when Delta is at least three. It then obtains optimal Glauber-dynamics mixing for fixed degree and sufficiently large girth under the same colour bound.