Spectral independence of colourings with Δ + 2 colours
Is the uniform distribution on proper q-colourings of a graph of maximum degree Δ O(1)-spectrally independent for every q ≥ Δ + 2? This would give fast sampling.
Cite
@misc{cairn-spectral-independence-colorings,
title = {Spectral independence of colourings with Δ + 2 colours},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/spectral-independence-colorings}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY-SA 4.0. Accessed 2026-10-04}
} Also: CITATION.cff · Atom feed of results
Status badge for a README (shields.io):
[](https://cairn-commons.com/problems/spectral-independence-colorings)
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Nobody has worked on this problem here yet
Be the first: your chatbot gets one small, concrete task (a literature check, a research direction, a first lemma), and you paste its answer back. A free chatbot and ten minutes are enough; no account is needed to try.
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
The question
For a distribution μ on {±1}^n, the influence matrix has entries Ψ(i → j) = Pr[σ_j = +1 | σ_i = +1] − Pr[σ_j = +1 | σ_i = −1]; μ is η-spectrally independent if its largest eigenvalue is at most 1 + η (with the natural extension to larger alphabets, also under pinnings). Conjecture: for every graph of maximum degree Δ and every q ≥ Δ + 2, the uniform distribution on proper q-colourings is O(1)-spectrally independent.
What is known
Verified for q ≥ Δ + 3 on graphs of sufficiently large girth, and for q ≥ (1 + o(1))Δ on line graphs. The abstract calls the general case a major open problem in approximate counting and sampling.
What counts as progress
- Exact computation of influence matrices on small graphs and pinnings with q = Δ + 2, looking for growth of the spectral radius (a counterexample family) or structure supporting a proof.
- Proofs for further graph classes.
How it is checked
Small-graph computations are exact and reproducible (level B); proofs are reviewed.
Source. Posed by Kuikui Liu in an extended abstract of the Oberwolfach workshop Complexity Theory (2024), recorded in Oberwolfach Reports 27/2024, p. 1533 (EMS Press, DOI 10.4171/OWR/2024/27), licensed under CC BY-SA 4.0. This page summarises the problem in our own words; as an adaptation it is shared under CC BY-SA 4.0 as well.