The large-q exponential-regime conjecture for sphere packing of proper colorings

From papers

Let qq be a positive integer. For a graph GG and proper qq-colorings of GG, call a set of colorings δ\delta-distinct when the colorings satisfy the paper's δ\delta-distinctness condition; let the exponential regime consist of parameter pairs (δ,λ)(\delta,\lambda) for which the corresponding extremal function ff has exponential growth, and let λ2\lambda_2 denote the second eigenvalue parameter of a dd-regular graph.

Large-q exponential-regime conjecture. For all qq sufficiently large, there exists an infinite sequence of dd-regular graphs with λ2=Θ(1/d)\lambda_2=\Theta(1/\sqrt{d}) for some d=Θ(q)d=\Theta(q) such that each graph has a δ\delta-distinct set of proper qq-colorings of exponential size for any δ<11/q\delta<1-1/q. In particular, (δ,λ)(\delta,\lambda) is in the exponential regime for all δ<11/q\delta<1-1/q and some λ=O(1/q)\lambda=O(1/\sqrt{q}).

This would show that, for sufficiently large numbers of colors, good expanders support exponentially many sufficiently separated proper colorings across essentially the full possible range of distinctness parameters. The claim is presented as an expectation for future work, and no resolution is given in the source.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Honglin Zhu, “Sphere packing proper colorings of an expander graph”, arXiv:2405.20368 (2025).

Solutions 0

No solutions have been posted yet.