Pith

open record

sign in

arxiv: 2604.18824 · v1 · submitted 2026-04-20 · math.CO

Symmetric and unimodal independence polynomials of trees

Takayuki Hibi , Selvi Kara , Dalena Vien This is my paper

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel 2026-05-10 03:40 UTCgrok-4.3open to challenge →

classification math.CO
keywords independence polynomialtreessymmetricunimodalgraph polynomialscombinatoricsindependent sets
0
0 comments X

The pith

Trees on n vertices exist with symmetric and unimodal independence polynomials, and some symmetric unimodal polynomials of degree n arise from trees.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines whether, for a given n, there is a tree on exactly n vertices whose independence polynomial has coefficients that are symmetric, reading the same forwards and backwards, and unimodal, increasing to a peak and then decreasing. It separately checks whether any given symmetric and unimodal polynomial of degree n can be realized as the independence polynomial of some tree. A reader would care because the independence polynomial records how many independent sets of each size exist in the graph, so symmetry and unimodality reveal a balanced distribution of set sizes that may be special to tree structures.

Core claim

We study the existence of a tree on n vertices whose independence polynomial is symmetric and unimodal as well as the existence of a symmetric and unimodal independence polynomial of degree n of a tree.

What carries the argument

The independence polynomial of a tree, the generating function whose coefficient of x^k counts the independent sets of size k, with its coefficient sequence checked for symmetry and unimodality.

If this is right

  • When such a tree exists for a given n, the counts of independent sets of complementary sizes must match exactly.
  • Unimodality in the polynomial implies the largest number of independent sets occurs near the middle size.
  • Realization of a symmetric unimodal polynomial of degree n as a tree polynomial shows that the set of tree independence polynomials intersects the set of all such sequences.
  • For n where existence holds, the tree can be constructed so its independent-set distribution satisfies both properties simultaneously.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The existence results could be used to generate families of trees whose independence polynomials avoid certain irregularities seen in general graphs.
  • Further checks on small n by direct computation of all trees would test the boundary cases where existence begins or fails.
  • The same symmetry-unimodality question might be posed for other acyclic graphs such as forests or caterpillars to see if the tree case is special.

Load-bearing premise

The definitions of symmetry and unimodality for independence polynomials of trees are compatible with the structural constraints of trees for some or all n.

What would settle it

An explicit n where every tree on n vertices has an independence polynomial that is either non-symmetric or non-unimodal, or a symmetric unimodal polynomial of degree n that is not the independence polynomial of any tree.

Figures

Figures reproduced from arXiv: 2604.18824 by Dalena Vien, Selvi Kara, Takayuki Hibi.

Figure 1
Figure 1. Figure 1: Rooted graphs (A, r),(B, s) and (C, t) from left to right Notice that ((A, r) ∨ (B, s)) ∨ (C, t) ̸= (A, r) ∨ ((B, s) ∨ (C, t)) as shown in [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: ((A, r) ∨ (B, s)) ∨ (C, t) (left) and (A, r) ∨ ((B, s) ∨ (C, t)) (right) polynomials, for our purposes it is convenient to adopt the following equivalent formulation. Set y = x (1 + x) 2 . Definition 1.3. A polynomial h(x) ∈ R[x] is called γ-positive if there exist an integer d ≥ 0 and nonnegative real numbers γ0, γ1, . . . , γ⌊d/2⌋ such that h(x) = ⌊ X d/2⌋ i=0 γix i (1 + x) d−2i . Equivalently, h(x) = (1… view at source ↗
Figure 3
Figure 3. Figure 3: The rooted tree (R19, r) A direct computation gives PR19 (x) = 1 + 19x + 153x 2 + 701x 3 + 2058x 4 + 4112x 5 + 5772x 6 + 5772x 7 + 4112x 8 + 2058x 9 + 701x 10 + 153x 11 + 19x 12 + x 13 = (1 + x) 13(1 + 6y + 9y 2 + 4y 3 + y 4 ) [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The rooted tree (R20, r) A direct computation gives PR20 (x) = 1 + 20x + 171x 2 + 829x 3 + 2548x 4 + 5255x 5 + 7496x 6 + 7496x 7 + 5255x 8 + 2548x 9 + 829x 10 + 171x 11 + 20x 12 + x 13 = (1 + x) 13(1 + 7y + 16y 2 + 14y 3 + 4y 4 ) and PR20−r(x) = 1 + 19x + 155x 2 + 722x 3 + 2151x 4 + 4343x 5 + 6129x 6 + 6129x 7 + 4343x 8 + 2151x 9 + 722x 10 + 155x 11 + 19x 12 + x 13 = (1 + x) 13(1 + 6y + 11y 2 + 7y 3 + y 4 … view at source ↗
Figure 5
Figure 5. Figure 5: The graph C(0, 1, 3, 0, 2, 0) = C(2, 3, 0, 3) Lemma 2.3. Let n ∈ [1, 18]. There is a tree T on n vertices such that PT (x) is symmetric and unimodal when n /∈ {2, 4, 5, 7, 10}. When n ∈ {2, 4, 5, 7, 10}, there is no tree with a symmetric independence polynomial. Proof. For n = 2, the only tree is P2 where PP2 (x) = 1 + 2x is not symmetric. For n ∈ {4, 5, 7, 10}, it was verified by a finite computer check u… view at source ↗
read the original abstract

Given $n \geq 1$, we study the existence of a tree on $n$ vertices whose independence polynomial is symmetric and unimodal as well as the existence of a symmetric and unimodal independence polynomial of degree $n$ of a tree.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript studies two existence questions for each integer n ≥ 1: whether there exists a tree on exactly n vertices whose independence polynomial is symmetric (palindromic coefficients) and unimodal, and whether there exists a symmetric and unimodal polynomial of degree n that arises as the independence polynomial of some tree (not necessarily on n vertices). The work proceeds via explicit constructions for small n, analysis of selected tree families, and non-existence arguments where applicable.

Significance. If the existence claims hold via the constructions and arguments, the paper contributes concrete examples and partial characterizations to the study of independence polynomials of trees, clarifying which coefficient sequences are realizable under the structural constraints of trees. The focus on both fixed-order trees and fixed-degree polynomials distinguishes the two questions and may guide further work on unimodal generating functions in graph theory.

minor comments (3)
  1. The abstract states the problems studied but does not summarize the main existence results or the values of n for which affirmative or negative answers are obtained; adding one sentence on the scope of the theorems would improve readability.
  2. In the definitions section, the precise statement of unimodality (strict or weak, and handling of plateaus) should be stated explicitly with reference to the coefficient sequence of I(T,x), as minor variations in definition can affect the constructions.
  3. Figure 1 (or the table of small-n examples) would benefit from an additional column listing the actual independence polynomial for each tree shown, to allow direct verification of symmetry and unimodality.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the supportive summary of our work on symmetric and unimodal independence polynomials of trees, the positive assessment of its significance, and the recommendation for minor revision. No specific major comments were listed in the report, so we have no point-by-point rebuttals to provide. We will incorporate any minor editorial suggestions in the revised version.

Circularity Check

0 steps flagged

No circularity: existence study with standard definitions

full rationale

The paper investigates existence of trees on n vertices with symmetric and unimodal independence polynomials (and symmetric unimodal polynomials of degree n arising from trees). It employs the standard definitions of symmetry (palindromic coefficient sequence) and unimodality without any derivation that reduces these properties to the paper's own constructions or fitted inputs. No equations, predictions, or self-citations are load-bearing in a way that creates circularity; the work proceeds via explicit constructions and non-existence arguments for small n and families, which are independent of the existence claims themselves. The derivation chain is self-contained against external combinatorial benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based solely on the abstract; no specific free parameters, ad-hoc axioms, or invented entities are introduced or mentioned.

axioms (2)
  • standard math Independence polynomials are defined for any graph and have non-negative integer coefficients.
    Standard definition in graph theory.
  • standard math Symmetry and unimodality are well-defined properties of polynomials with real coefficients.
    Basic algebraic properties.

pith-pipeline@v0.9.0 · 5319 in / 1052 out tokens · 41491 ms · 2026-05-10T03:40:49.706414+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    Alavi, P

    Y. Alavi, P. J. Malde, A. J. Schwenk, and P. Erd˝ os. The vertex independence sequence of a graph is not constrained. volume 58, pages 15–23. 1987. Eighteenth Southeast- ern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, Fla., 1987)

    work page 1987

  2. [2]

    C. A. Athanasiadis. Gamma-positivity in combinatorics and geometry.S´ em. Lothar. Combin., 77:Art. B77i, 64, 2016–2018

    work page 2016

  3. [3]

    C. A. Athanasiadis. Binomial Eulerian polynomials for colored permutations.J. Combin. Theory Ser. A, 173:105214, 38, 2020. 10

    work page 2020

  4. [4]

    Bencs, P

    F. Bencs, P. Csikv´ ari, P. Srivastava, and J. Vondr´ ak. On complex roots of the inde- pendence polynomial. InProceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 675–699. SIAM, Philadelphia, PA, 2023

    work page 2023

  5. [5]

    Br¨ and´ en

    P. Br¨ and´ en. Actions on permutations and unimodality of descent polynomials.European J. Combin., 29(2):514–531, 2008

    work page 2008

  6. [6]

    J. I. Brown and B. Cameron. On the unimodality of independence polynomials of very well-covered graphs.Discrete Math., 341(4):1138–1143, 2018

    work page 2018

  7. [7]

    J. I. Brown, C. A. Hickman, and R. J. Nowakowski. On the location of roots of inde- pendence polynomials.J. Algebraic Combin., 19(3):273–282, 2004

    work page 2004

  8. [8]

    Chudnovsky and P

    M. Chudnovsky and P. Seymour. The roots of the independence polynomial of a clawfree graph.J. Combin. Theory Ser. B, 97(3):350–357, 2007

    work page 2007

  9. [9]

    Foata and M.-P

    D. Foata and M.-P. Sch¨ utzenberger.Th´ eorie g´ eom´ etrique des polynˆ omes eul´ eriens, volume Vol. 138 ofLecture Notes in Mathematics. Springer-Verlag, Berlin-New York, 1970

    work page 1970

  10. [10]

    T. Hibi, S. Kara, and D. Vien. Independence polynomials of graphs, 2026

    work page 2026

  11. [11]

    V. E. Levit and E. Mandrescu. The cyclomatic number of a graph and its independence polynomial at−1.Graphs Combin., 29(2):259–273, 2013

    work page 2013

  12. [12]

    Lin and J

    Z. Lin and J. Zeng. Theγ-positivity of basic Eulerian polynomials via group actions. J. Combin. Theory Ser. A, 135:112–129, 2015

    work page 2015

  13. [13]

    Mandrescu

    E. Mandrescu. Unimodality of some independence polynomials via their palindromicity. Australas. J. Combin., 53:77–82, 2012

    work page 2012

  14. [14]

    Postnikov, V

    A. Postnikov, V. Reiner, and L. Williams. Faces of generalized permutohedra.Doc. Math., 13:207–273, 2008

    work page 2008

  15. [15]

    Reynolds

    B. Reynolds. Mean bounds, structural reductions, and exhaustive verification for tree independence polynomial unimodality, Mar. 2026. Preprint, Zenodo, version v3

    work page 2026

  16. [16]

    Shareshian and M

    J. Shareshian and M. L. Wachs. Gamma-positivity of variations of Eulerian polynomials. J. Comb., 11(1):1–33, 2020

    work page 2020

  17. [17]

    Stevanovi´ c

    D. Stevanovi´ c. Graphs with palindromic independence polynomial. volume 34, pages 31–36. 1998. New York Graph Theory Day, 34 (1997). (T. Hibi)Department of Pure and Applied Mathematics, Graduate School of Information Science and Technology, Osaka University, Suita, Osaka 565–0871, Japan Email address:hibi@math.sci.osaka-u.ac.jp (S. Kara)Department of Mat...

    work page 1998