The tree-coloring strong spatial mixing conjecture

Let TT) be a tree of maximum degree Δ\Delta, and let qq be the number of colors. The uniform distribution on proper qq-colorings of TT is considered with strong spatial mixing (SSM), meaning that the influence of differing boundary pinnings on a vertex's marginal decays exponentially in their distance. Tree-coloring SSM conjecture. For qΔ+1q \geq \Delta+1, the uniform distribution on qq-colorings on trees of maximum degree Δ\Delta exhibits strong spatial mixing with exponential decay rate. This is a basic unresolved question even on trees and is closely connected to understanding correlations in random colorings and to algorithmic sampling.

Sources & referencesView supporting material

Primary source

Zongchen Chen, Kuikui Liu, Nitya Mani and Ankur Moitra, “Strong spatial mixing for colorings on trees and its algorithmic applications”, arXiv:2304.01954 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.