A Bipartite Graph with a Nonunimodal Acyclic Polynomial
Version 1 / Oct 18, 2026 / CC BY 4.0
Abstract
We construct a bipartite graph on 230 vertices whose acyclic polynomial, which enumerates vertex subsets inducing forests, is not unimodal. This answers Question 3.3 of Barton, Brown, and Pike negatively. The graph has a common set of 50 vertices and 15 branches, each with two sets of six vertices. A partition according to the number of selected common vertices gives a three-term formula for the complete induced-forest polynomial. Its coefficients have a strict descent from degree 62 to degree 63 and a later strict ascent from degree 66 to degree 67. The actual graph, the unrestricted subset-counting formula, and the exact inequalities have been checked in Lean. HAL deposit: hal-05800225v1.
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