The tree-coloring strong spatial mixing conjecture
The tree-coloring strong spatial mixing conjecture
Let ) be a tree of maximum degree , and let be the number of colors. The uniform distribution on proper -colorings of 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 , the uniform distribution on -colorings on trees of maximum degree 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.