Superexponential chromatic evaluation spectrum at -1

About 1 year old · traced to

For each integer n≥1n\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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.