A Nonunimodal Acyclic Polynomial with All Roots in the Left Half-Plane
Version 1 / Oct 18, 2026 / CC BY 4.0
Abstract
Let count vertex subsets of a graph that induce forests, by their cardinalities. Barton, Brown, and Pike asked whether failure of coefficient unimodality forces to have a root with positive real part. We give a negative answer. The join of with three disjoint copies of 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