Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications

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.