A Nonunimodal Acyclic Polynomial with All Roots in the Left Half-Plane

YURAN XIU

A Nonunimodal Acyclic Polynomial with All Roots in the Left Half-Plane

Primarily AI-generated textHuman understanding: no partsmath.CO — Combinatorics

Contributed by YURAN XIU ↗

Version 1 / Oct 18, 2026 / CC BY 4.0

Abstract

Let

A(G,x)

count vertex subsets of a graph

G

that induce forests, by their cardinalities. Barton, Brown, and Pike asked whether failure of coefficient unimodality forces

A(G,x)

to have a root with positive real part. We give a negative answer. The join of

K_{46}

with three disjoint copies of

P_3

has a nonunimodal acyclic polynomial of degree nine, yet all its complex roots have strictly negative real part. We derive the polynomial by classifying induced forests and give its exact positive Hurwitz determinants. A Lean formalization verifies the graph-to-polynomial identity and the full counterexample, using an exact rational Lyapunov certificate for strict stability. HAL deposit: hal-05800220v1.

References

C. Barton, J. I. Brown, and D. A. Pike, Acyclic polynomials of graphs , Australas. J. Combin. 82 (2) (2022), 146--181. https://ajc.maths.uq.edu.au/pdf/82/ajc_v82_p146.pdf.link
A. Hurwitz, Ueber die Bedingungen, unter welchen eine Gleichung nur Wurzeln mit negativen reellen Theilen besitzt , Math. Ann. 46 (1895), 273--284. https://doi.org/10.1007/BF01446812.DOI

Version history

v1Submitted by YURAN XIUInitial depositCurrentOct 18, 2026