Nonexistence of almost-complete Harary polynomials

From papers

Let G(n,1/2)\mathbb{G}(n,1/2) be the random graph model with edge probability 1/21/2, and let a Harary polynomial be a graph polynomial arising from a graph property. A graph polynomial is almost complete when asymptotically almost all graphs in the model are uniquely determined by it.

Harary almost-completeness conjecture. There is no Harary polynomial which is almost complete for G(n,1/2)\mathbb{G}(n,1/2).

This is proposed in contrast with the Bollobás–Pebody–Riordan conjecture for the chromatic polynomial. The supplied text gives no resolution or supporting theorem for this stronger nonexistence claim.

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

Johann A. Makowsky, “Distinctive power and comparability of Harary polynomial”, arXiv:2512.22556 (2025).

Solutions 0

No solutions have been posted yet.