The large-q exponential-regime conjecture for sphere packing of proper colorings
The large-q exponential-regime conjecture for sphere packing of proper colorings
Let be a positive integer. For a graph and proper -colorings of , call a set of colorings -distinct when the colorings satisfy the paper's -distinctness condition; let the exponential regime consist of parameter pairs for which the corresponding extremal function has exponential growth, and let denote the second eigenvalue parameter of a -regular graph.
Large-q exponential-regime conjecture. For all sufficiently large, there exists an infinite sequence of -regular graphs with for some such that each graph has a -distinct set of proper -colorings of exponential size for any . In particular, is in the exponential regime for all and some .
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
Sign in to submit a solution.
No solutions have been posted yet.