Symmetric and unimodal independence polynomials of trees

Takayuki Hibi, Selvi Kara, Dalena Vien · 2026

Read Symmetric and unimodal independence polynomials of trees by Takayuki Hibi, Selvi Kara, Dalena Vien (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-18824.txt.

Introduction

Hibi, Kara, and Vien study, for each n, whether a tree on n nodes has a symmetric and unimodal independence polynomial. They also ask whether a symmetric and unimodal independence polynomial of degree n arises from a tree. The independence polynomial of a graph counts its independent sets by size. Symmetric means the coefficients read the same forwards and backwards, and unimodal means they rise and then fall.

Catalog record

CREATORTakayuki Hibi, Selvi Kara, Dalena Vien
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE18171
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.18824

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Symmetric and unimodal independence polynomials of trees Thanks: The research for the present paper was initiated while the first author visited Bryn Mawr College, Pennsylvania, February 28 – March 21, 2026. Takayuki Hibi, Selvi Kara, Dalena Vien Abstract . Given n ≥ 1 n\geq 1 , we study the existence of a tree on n n vertices whose independence polynomial is symmetric and unimodal as well as the existence of a symmetric and unimodal independence polynomial of degree n n of a tree. 2020 Mathematics Subject Classification 05C30, 05C31 Introduction Every graph considered in this paper is finite and simple. For a graph G , let g_{i}(G) denote the number of independent sets of G of cardinality i . The independence polynomial of G is P_{G}(x)=\sum_{i\geq 0}g_{i}(G)x^{i}. Equivalently, independence polynomials are the face polynomials of independence complexes of graphs, and are therefore closely related to the study of face vectors of flag complexes. They have been studied extensively from several points of view [ 11 , 6 , 7 , 4 , 8 ] in graph theory. In 1987 [ 1 ] , Alavi, Malde, Schwenk, and Erdős conjectured that the independence polynomials of trees are unimodal. As of April 2026, the conjecture remains open in general, and has been computationally verified for trees on at most 29 vertices [ 15 ] . Motivated by this problem, we study the existence of trees whose independence polynomials are symmetric and unimodal. A finite sequence a_{0},a_{1},\ldots,a_{d} of nonnegative integers is called symmetric if a_{i}=a_{d-i} for each 0\leq i\leq d . A symmetric sequence a_{0},a_{1},\ldots,a_{d} is called unimodal if a_{0}\leq a_{1}\leq\cdots\leq a_{\lfloor d/2\rfloor} . A polynomial P(x)=a_{0}+a_{1}x+\cdots+a_{d}x^{d} with a_{i}\in\mathbb{Z}_{\geq 0} is called symmetric (resp. unimodal ) if its coefficient sequence is symmetric (resp. unimodal). More precisely, we address two existence questions. First, for which integers n does there exist a tree on n vertices whose independence polynomial is symmetric and unimodal? Second, for which integers d does there exist a tree whose independence polynomial is symmetric and unimodal of degree d ? Our method combines two ingredients. The first is a new gluing construction for rooted graphs, introduced in the Bridge Lemma (Lemma 1 ). This lemma allows us to construct larger rooted trees from smaller ones while preserving the structure needed in our arguments. The second is the \gamma -positivity viewpoint for symmetric polynomials. If h(x) is symmetric with center of symmetry d/2 , then it admits a unique expansion h(x)=\sum_{i=0}^{\lfloor d/2\rfloor}\gamma_{i}x^{i}(1+x)^{d-2i}. When all \gamma_{i} are nonnegative, the polynomial h(x) is said to be \gamma -positive. This viewpoint provides a convenient route to unimodality; see [ 2 ] . In the body of the paper, we adapt it to rooted trees through the notion of \gamma -admissibility. The notion of \gamma -positivity appeared first in the work of D. Foata and M. Schützenberger [ 9 ] and it is extremely useful as it directly implies symmetry and unimodality. This application of \gamma -positivity appears widely in combinatorial and geometric contexts (see [ 3 , 5 , 12 , 14 , 16 ] ). The main result of the present paper is the following. Theorem 0.1 . (1) Given n\geq 1 with n\notin\{2,4,5,7,10\} , there is a tree on n vertices whose independence polynomial is symmetric and unimodal. (2) Given d\geq 1 with d\neq 3 , there is a tree whose independence polynomial is symmetric and unimodal of degree d . 1. Bridge Lemma In this section, we introduce a new technique to construct symmetric independence polynomials of trees. Given a graph G and a vertex r\in V(G) , the rooted graph (G,r) is the graph G with vertex r viewed as a root. Each vertex of G can be chosen as a root. Definition 1.1 . Given two rooted graphs (G,r) and (H,s) , the bridging of (G,r) and (H,s) , denoted by (G,r)\vee(H,s) , is the rooted graph with r its root which is obtained from the disjoint union of (G,r) and (H,s) by adding the edge \{r,s\} . Remark 1.2 . Bridging is not necessarily associative. Let (A,r),(B,s) , and (C,t) be rooted graphs given in Figure 1 . Figure 1. Rooted graphs (A,r),(B,s) and (C,t) from left to right Notice that ((A,r)\vee(B,s))\vee(C,t)\neq(A,r)\vee((B,s)\vee(C,t)) as shown in Figure 2 . Figure 2. ((A,r)\vee(B,s))\vee(C,t) (left) and (A,r)\vee((B,s)\vee(C,t)) (right) To obtain symmetric and unimodal independence polynomials, we use \gamma -positivity (see [ 2 ] . for a survey on \gamma -positivity). Although \gamma -positivity is usually introduced for symmetric polynomials, for our purposes it is convenient to adopt the following equivalent formulation. Set y=\frac{x}{(1+x)^{2}}. Definition 1.3 . A polynomial h(x)\in\mathbb{R}[x] is called \gamma -positive if there exist an integer d\geq 0 and nonnegative real numbers \gamma_{0},\gamma_{1},\ldots,\gamma_{\lfloor d/2\rfloor} such that h(x)=\sum_{i=0}^{\lfloor d/2\rfloor}\gamma_{i}x^{i}(1+x)^{d-2i}. Equivalently, h(x)=(1+x)^{d}~\Gamma_{h}(y) where \Gamma_{h}(y)=\sum_{i=0}^{\lfloor d/2\rfloor}\gamma_{i}y^{i}\in\mathbb{R}_{\geq 0}[y] . The following is well-known in the literature but we include it here for completeness. Lemma 1.4 . If h(x) is \gamma -positive, then h(x) is symmetric and unimodal. If, in addition, h(0)\neq 0 , then \deg h(x)=d . Proof. Since the substitution x\mapsto 1/x leaves y invariant, we have x^{d}h(1/x)=x^{d}\Bigl(1+\frac{1}{x}\Bigr)^{d}~\Gamma_{h}\left(\frac{1/x}{(1+1/x)^{2}}\right)=(1+x)^{d}~\Gamma_{h}(y)=h(x). Thus h(x) is symmetric with center of symmetry d/2 . Moreover, each polynomial x^{i}(1+x)^{d-2i} has coefficient sequence obtained from that of (1+x)^{d-2i} by padding with i zeros at the beginning and at the end. Hence each x^{i}(1+x)^{d-2i} is symmetric and unimodal with center of symmetry d/2 . Since h(x) is a nonnegative linear combination of these polynomials, it follows that h(x) is unimodal. Finally, if h(0)\neq 0 , then \gamma_{0}=h(0)>0 . Thus the term \gamma_{0}(1+x)^{d} occurs with positive coefficient. Therefore \deg h(x)=d . ∎ Remark 1.5 . Let G be any finite simple graph and H=G\circ 2K_{1} be the graph obtained by joining each vertex of G to two new vertices. It is known that H has a symmetric independence polynomial [ 17 , 10 ] . Moreover, it was shown in [ 13 ] that the independence polynomial of H is unimodal. It can also be easily verified that P_{H}(x) is \gamma -positive. This follows from observing that P_{H}(x)=\sum_{i=0}^{\alpha(G)}g_{i}x^{i}(1+x)^{2n-2i} where |V(G)|=n and g_{i} is the number of independent sets of size i in G . We now introduce the notion of \gamma -admissibility for rooted graphs. Definition 1.6 . A rooted graph (G,r) is called \gamma -admissible if there exist an integer d\geq 0 and polynomials A(y),B(y)\in\mathbb{Z}_{\geq 0}[y] such that P_{G}(x)=(1+x)^{d}A(y),\qquad P_{G-r}(x)=(1+x)^{d}B(y). Example 1.7 . Let R_{3}=P_{3} be rooted at its middle vertex r . Then (R_{3},r) is \gamma -admissible since P_{R_{3}}(x)=1+3x+x^{2}=(1+x)^{2}(1+y),\qquad P_{R_{3}-r}(x)=1+2x+x^{2}=(1+x)^{2} where A(y)=1+y and B(y)=1 such that A(y)-B(y)=y\in\mathbb{Z}_{\geq 0}[y] . Remark 1.8 . If (G,r) is \gamma -admissible, one has x^{d}P_{G}(1/x)=P_{G}(x),\qquad x^{d}P_{G-r}(1/x)=P_{G-r}(x). This implies that both P_{G}(x) and P_{G-r}(x) have degree d since independence polynomials have constant term 1 . Since P_{G}(x) and P_{G-r}(x) are symmetric of degree d , by the standard theory of \gamma -positivity for symmetric polynomials (see [ 2 ] ), there are unique coefficients a_{0},\dots,a_{\lfloor d/2\rfloor}\in\mathbb{Z}_{\geq 0} and b_{0},\dots,b_{\lfloor d/2\rfloor}\in\mathbb{Z}_{\geq 0} such that A(y)=\sum_{i=0}^{\lfloor d/2\rfloor}a_{i}y^{i},\qquad B(y)=\sum_{i=0}^{\lfloor d/2\rfloor}b_{i}y^{i}. Therefore, P_{G}(x) and P_{G-r}(x) are \gamma -positive. Hence, both are symmetric and unimodal by Section 1 . The following result, which we refer to as Bridge Lemma , is useful in creating symmetric and unimodal independence polynomials for larger graphs

Read the complete text