The tree-coloring strong spatial mixing conjecture

About 3 years old · traced to

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.

References

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.