Abstract

Strong spatial mixing (SSM) is an important quantitative notion of correlation decay for Gibbs distributions arising in statistical physics, probability theory, and theoretical computer science. A longstanding conjecture is that the uniform distribution on proper q-colorings on a D-regular tree exhibits SSM whenever q >= D+1. Moreover, it is widely believed that as long as SSM holds on bounded-degree trees with q colors, one would obtain an efficient sampler for q-colorings on all bounded-degree graphs via simple Markov chain algorithms. We show SSM for q-colorings on all trees of maximum degree D whenever q >= D+3, almost fully resolving the first conjecture. Towards sampling, we establish optimal mixing of the Glauber dynamics for q-colorings on all graphs of maximum degree D and sufficiently large girth whenever q >= D+3. Joint work with Kuikui Liu, Nitya Mani, and Ankur Moitra.

Time

2023-11-30  10:00 - 11:00   

Speaker

Zongchen Chen, University at Buffalo

Room

Room 308