Superexponential chromatic evaluation spectrum at -1

From papers

For each integer n1n\geq 1, let Sn(1)={PG(1):G is a simple graph on n vertices}\mathsf{S}_n(-1)=\{P_G(-1):G\text{ is a simple graph on }n\text{ vertices}\}. Since PG(1)|P_G(-1)| counts acyclic orientations of GG, the spectrum can in principle have an upper bound as large as PKn(1)=n!|P_{K_n}(-1)|=n!. Superexponential spectrum conjecture. The cardinality Sn(1)|\mathsf{S}_n(-1)| is superexponential in nn. This asks whether the distinct numbers of acyclic orientations, viewed through chromatic-polynomial evaluations, occur in superexponentially many values; the paper leaves the question open.

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

Rafael Miyazaki, Cosmin Pohoata and Michael Zheng, “Chromatic Polynomial Evaluation Spectra”, arXiv:2512.19600 (2025).

Solutions 0

No solutions have been posted yet.