Folklore coupling-independence conjecture for proper list-colorings

Let G=(V,E)G=(V,E) be a graph with maximum degree Δ\Delta, and let (Lv)vV(L_v)_{v\in V} be color lists. A proper list-coloring assigns to each vertex vv a color in LvL_v so that adjacent vertices receive different colors. The associated uniform distribution is called Oδ(1)O_\delta(1)-coupling independent when its coupling-independence parameter is bounded by a constant depending only on δ\delta.

Folklore conjecture. Let δ>0\delta>0 be a constant. If

Lv(1+δ)Δ+O(1)\left\vert L_v\right\vert\geq (1+\delta)\Delta+O(1)

for every vVv\in V, then the uniform distribution μ\mu over all proper list-colorings of GG is Oδ(1)O_\delta(1)-coupling independent.

This conjecture would establish coupling independence at essentially the (1+δ)Δ(1+\delta)\Delta list-size threshold for arbitrary, possibly unbounded-degree graphs, and would remove the stronger color-list requirement used by the paper's main rapid-mixing result. The source gives no resolution of the conjecture.

Sources & referencesView supporting material

Primary source

Xiaoyu Chen and Weiming Feng, “Rapid Mixing via Coupling Independence for Spin Systems with Unbounded Degree”, arXiv:2407.04672 (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.