Multiple breaks of log-concavity in the independence polynomials of trees
César Bautista-Ramos · 2025
Read Multiple breaks of log-concavity in the independence polynomials of trees by César Bautista-Ramos (2025) 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-2511-00334.txt.
Introduction
César Bautista-Ramos answers a question posed by D Galvin about independence polynomials of trees. An independence polynomial counts the sets of vertices in a graph with no two joined by an edge, grouped by set size. Log-concavity, a smoothness property of those counts, was once hoped to hold broadly. Bautista-Ramos builds endless families of trees whose polynomials break log-concavity at any chosen number of positions, as many as desired.
Catalog record
| CREATOR | César Bautista-Ramos |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 11 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-00334
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Multiple breaks of log-concavity in the independence polynomials of trees César Bautista-Ramos Abstract . We construct infinite families of trees whose independence polynomials violate log-concavity at an arbitrary number of indices. This affirmatively answers a question of D. Galvin. 2020 Mathematics Subject Classification Primary 05C05, 05C31, 05A15, 30C15; Secondary 05C76, 11B83 1. Introduction The conjecture that independence polynomials of trees are unimodal [ 1 ] was later strengthened to the more tractable conjecture that they are log-concave [ 9 ] . Several authors have since disproven this [ 7 , 6 , 4 , 10 ] . At the time of this writing, all known counterexamples in the literature exhibited only a single break in log-concavity. This observation led Galvin [ 4 ] to ask whether multiple breaks are possible. In this note, we answer that question affirmatively. We construct infinite families of trees whose independence polynomials break log-concavity at an arbitrary number of indices (Theorem 1 ). 2. Definitions and Results We use standard definitions, notations, and concepts from the literature concerning independent sets in simple graphs and the log-concavity of sequences (see, for instance, [ 7 , 4 ] ). In particular, if G is a graph and v is a vertex of G , we use N[v] to denote the closed neighborhood of v , while G\setminus v and G\setminus N[v] denote the corresponding graphs with those vertices deleted. We denote the independence polynomial of a graph G in the indeterminate x by I(G) . The degree of I(G) is the independence number of the graph, denoted \alpha(G) . We also use the standard recursive formulas for computing the independence polynomial [ 2 , 5 ] . For a simple graph G and a vertex v of G , I(G)=I(G\setminus v)+x\,I(G\setminus N[v]). (1) If G is the disjoint union of graphs G_{1} and G_{2} , then I(G)=I(G_{1})I(G_{2}). (2) In the following, we define the trees TG_{m,t} that exhibit as many as m violations of the log-concavity of their independence polynomials. Definition 1 . Let m and t be two nonnegative integers. (i) Let P_{m} denote the path graph on m vertices. (ii) Let S_{2,m} denote the starlike graph with a root w to which m copies of P_{2} are attached. (iii) The tree T_{m,t} is defined as the tree with a root v that has m children, and each child has t pendant P_{2} paths. (iv) The tree TG_{m,t} is obtained by taking m disjoint copies of T_{3,t} , joining the root v of each copy to a new root v_{0} , and adding one additional child to v_{0} that has no further descendants. The trees T_{m,t} and S_{2,t} were first defined by Galvin [ 4 ] in order to prove a conjecture of Kadrawi and Levit [ 6 ] . Fig. 1 shows the tree TG_{2,5} , whose independence polynomial is non-log-concave, with violations at two indices. In what follows, we explain why. v_{0} v v Figure 1. The tree TG_{2,5} , whose independence polynomial has degree 37 and breaks log-concavity at indices 34 and 36. For TG_{m,t} , the parameter m equals the number of log-concavity violations for sufficiently large t . The equations I(P_{1})=1+x , I(P_{2})=1+2x , together with ( 1 ) and ( 2 ), yield the following. Lemma 1 . Let m and t be two nonnegative integers. Then, I(S_{2,t})=I(P_{2})^{t}+xI(P_{1})^{t},\quad I(T_{m,t})=S_{2,t}^{m}+xP_{2}^{mt} (3) and \alpha(S_{2,t})=t+1 , \alpha(T_{m,t})=m(t+1) . The trees in [ 7 , 6 , 10 ] have independence polynomials whose log-concavity is broken near the leading coefficient. A similar phenomenon occurs for our trees TG_{m,t} . To expose the relevant coefficients, it is convenient to consider the reflected independence polynomials. Definition 2 . Let p\in\mathbb{Z}[x] be a polynomial. The reflected polynomial of p , denoted by Rp , is defined as Rp(x)=x^{n}p(1/x), where n=\deg p . From the definition, it follows that the reflection operator R is multiplicative: for any polynomials p,q\in\mathbb{Z}[x] , we have R(pq)=(Rp)(Rq). Additionally, R satisfies an additive property under certain conditions: If \deg(p+q)=\deg p , then R(p+q)=Rp+x^{\deg p-\deg q}Rq. Applying ( 1 ) to the root vertex v_{0} of TG_{m,t} yields I(TG_{m,t})=I(P_{1})I(T_{3,t})^{m}+xI(S_{2,t})^{3m}, (4) which implies, together with Lemma 1 , that \alpha(TG_{m,t})=3(t+1)m+1 . We now define the coefficients of the reflected independence polynomial of TG_{m,t} . Definition 3 . Let c_{k}(m,t)\in\mathbb{Z} be such that RI(TG_{m,t})=\sum_{k=0}^{\infty}c_{k}(m,t)x^{k}. We can compute the first few coefficients c_{k}(m,t) as follows. After applying the reflection operator to both sides of ( 4 ) and using its additive and multiplicative properties together with Lemma 1 , we obtain RI(TG_{m,t})=(x+1)RI(T_{3,t})^{m}+RI(S_{2,t})^{3m}. (5) Furthermore, from Lemma 1 , we use the equations RI(T_{3,t})=RI(S_{2,t})^{3}+x^{2}(x+2)^{3t},\quad RI(S_{2,t})=(x+1)^{t}+x(x+2)^{t}, (6) where we expand (x+2)^{t} and (x+1)^{t} using the binomial theorem. However, we are only interested in the highest-order terms. To this end, we use the exact-order \Theta asymptotic notation [ 3 , p. 87] , [ 8 , p. 110] . Definition 4 . Let A=(a_{k}(t))_{k=0}^{\infty} and B=(b_{k}(t))_{k=0}^{\infty} be sequences where each term is an eventually nonnegative function of the positive integer variable t . Let S_{A}(x) and S_{B}(x) be their respective generating functions with indeterminate x , and let m be a fixed positive integer. We write S_{A}(x)\asymp S_{B}(x)\pmod{x^{m}} if a_{k}(t)\in\Theta(b_{k}(t)) for all 0\leq k\leq m-1 . The relation \asymp is an equivalence relation because this property is inherited from the exact-order relation \Theta . Furthermore, \asymp is consistent with the sum and product of generating functions in the following sense. Proposition 1 . Let m be a fixed positive integer. Let A,B,C,D be four sequences of eventually nonnegative functions of the positive integer variable t . If S_{A}(x)\asymp S_{C}(x)\text{ and }S_{B}(x)\asymp S_{D}(x)\pmod{x^{m}} then S_{A}(x)+S_{B}(x)\asymp S_{C}(x)+S_{D}(x)\text{ and }S_{A}(x)S_{B}(x)\asymp S_{C}(x)S_{D}(x)\pmod{x^{m}}. The proof of this proposition is elementary, so we omit it. This proposition is used frequently in the proof of the following lemma. Lemma 2 . Let m be a fixed positive integer and let t be a positive integer variable. Then: (i) (2+x)^{t}\asymp 2^{t}(1+x)^{t}\pmod{x^{m}} . (ii) (2+x)^{t}(1+x)\asymp(2+x)^{t}\pmod{x^{m}} . (iii) (1+2^{t}x)^{m}(1+x)\asymp(1+2^{t}x)^{m}\pmod{x^{m+1}} . (iv) RI(S_{2,t})\asymp 1+2^{t}x(1+x)^{t}\pmod{x^{m}} . (v) RI(S_{2,t})^{3}\asymp(1+2^{t}x)^{2}+x^{3}(2+x)^{3t}\pmod{x^{m}} . (vi) RI(T_{3,t})\asymp(1+2^{t}x)^{2}+x^{2}(2+x)^{3t}\pmod{x^{m}} . (vii) RI(T_{3,t})^{m}(x+1)\asymp\sum_{k=0}^{\infty}2^{(k+\lfloor k/2\rfloor)t}\pmod{x^{2m+1}} . (viii) RI(S_{2,t})^{3m}\asymp\sum_{k=0}^{\infty}2^{kt}x^{k}\pmod{x^{2m+1}} . Proof. (i) From the binomial theorem and using that \binom{t}{k}\in\Theta(t^{k}) for 0\leq k\leq m-1 , the result follows. (ii) Using ( i ) and (1+x)^{t+1}\asymp(1+x)^{t}\pmod{x^{m}} , we obtain the result. (iii) From the binomial theorem, \displaystyle(1+2^{t}x)^{m}(1+x) \displaystyle\asymp\sum_{j=0}^{m}2^{jt}x^{j}+\sum_{j=0}^{m}2^{jt}x^{j+1} \displaystyle\asymp 1+\sum_{j=1}^{m}(2^{jt}+2^{(j-1)t})x^{j}+2^{mt}x^{m+1} \displaystyle\asymp(1+2^{t}x)^{m}\pmod{x^{m+1}}. (iv) From ( 6 ) and ( i ) we obtain: \displaystyle RI(S_{2,t}) \displaystyle\asymp(1+x)^{t}(1+2^{t}x)\asymp\sum_{k=0}^{\infty}t^{k}x^{k}+\sum_{k=0}^{\infty}2^{t}t^{k}x^{k+1} \displaystyle\asymp 1+\sum_{k=1}^{\infty}(t^{k}+2^{t}t^{k-1})x^{k}\asymp 1+2^{t}x(1+x)^{t}\pmod{x^{m}}. (v) From ( iv ), the binomial theorem, and ( i ), we obtain: \displaystyle RI(S_{2,t})^{3} \displaystyle\asymp 1+x2^{t}(1+x)^{t}+x^{2}2^{2t}(1+x)^{2t}+x^{3}2^{3t}(1+x)^{3t} \displaystyle\asymp 1+\sum_{k=0}^{\infty}2^{t}t^{k}x^{k+1}+\sum_{k=0}^{\infty}2^{2t}t^{k}x^{k+2}+\sum_{k=0}^{\infty}2^{3t}t^{k}x^{k+3} \displaystyle\asymp 1+2^{t}x+(t2^{t}+2^{2t})x^{2}+\sum_{k=3}^{\infty}(2^{t}t^{k-1}+2^{2t}t^{k-2}+2^{3t}t^{k-3})x^{k} \displaystyle\asymp(1+2^{t}x)^{2}+x^{3}(2+x)^{3t}\pmod{x^{m}}. (vi) From ( 6 ), ( v ), and ( ii ), we obtain: \displaystyle RI(T_{3,t}) \displaystyle\asymp(1+2^{t}x)^{2}+x^{3}(2+x)^{3t}+x^{2}(2+x)^{3t} \displaystyle\asymp(1+2^{t}x)^{2}+x^{2}(2+x)^{3t}(1+x) \displaystyle\asymp(1+2^{t}x)^{2}+x^{2}(2+x)^{3t}\pmod{x^{2m+1}}, where we work modulo x^{2m+1} in preparation for the proof of ( vii ). (vii) By ( vi ) and the binomial theorem, we obtain \displaystyle RI \displaystyle(T_{3,t})^{m}(1+x)\asymp(1+2^{t}x)^{2m}(1+x)+ \displaystyle\,\sum_{j=1}^{m}(1+2^{t}x)^{2(m-j)}x^{2j}(x+2)^{3jt}(1+x)\pmod{x^{2m+1}}. From ( iii ) and ( ii ), we know that the factor 1+x can be ignored. Thus, using ( i ), we can write \displaystyle RI(T_{3,t})^{m}(1+x) \displaystyle\asymp\sum_{j=0}^{m}(1+2^{t}x)^{2(m-j)}x^{2j}(2+x)^{3jt} \displaystyle\asymp\left(\sum_{k=0}^{\infty}t^{k}x^{k}\right)Q\pmod{x^{2m+1}}, where Q=\sum_{j=0}^{m}\sum_{k=0}^{2(m-j)}2^{(3j+k)t}x^{2j+k}. In order to find the exact order of the coefficients of Q , we make the change of variables \ell=2j+k. (7) We must determine the coefficients of each monomial x^{\ell} . Observe that \ell+j=3j+k