Exponent gap for frozen (Δ+1)-colourings

Status open high confidence

Theorem 1 of arXiv:1811.12650 gives the upper bound $(6/7)^{n/(\Delta+1)}$ on the probability that a uniform random $(\Delta+1)$-colouring is frozen, while Proposition 4 provides a matching lower bound with exponent $e^{-3\log(\Delta)/\Delta \cdot n}$, leaving a gap of a $\log\Delta$ factor in the exponent. The authors believe the upper bound can be tightened to close this gap. No follow-up paper improving or resolving this exponent gap was found in any indexed literature searched.

Reviewer notes. No follow-up found improving the log(Delta) gap in the exponent. The conjecture states informally that the dependence on Delta in the exponent of (6/7)^{n/(Delta+1)} is not best possible; the matching lower bound has exponent e^{-3 log(Delta)/Delta * n}, so the gap is a factor of log(Delta). Semantic Scholar API returned zero citations, and targeted web searches found no subsequent paper closing or narrowing this gap.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).