Unimodality of Independence Polynomials of Special Trees

By
Kaixin Wang
-
0
2634

Read the full article as a PDFDownload

Abstract

This paper discusses two approaches to tackling problems in extremal graph theory about the relative sizes of cliques and independent sets. We will employ combinatorial and algebraic approaches.

A tree (and its independence polynomial) is unimodal whenever the number of independent sets of size t monotonically increases until one point , called the mode, from which it monotonically decreases afterwards as t goes from 0 to the size of the largest independent set. Since a tree has a lot of recursive properties, it is helpful to think of the independence polynomial I(T;x)=\sum\limits_{j=0}^{\alpha(T)} i_j(T)x^j, where \alpha(T) is the size of the largest independent set in T and i_j(T) is the number of independent sets of size j in T.

In 1987, Alavi, Malde, Schwenk and Erd\H{o}s conjectured that the independence polynomial of every tree is unimodal1. In this paper, we confirm some special cases of this conjecture.

Introduction

Graph theory has become a popular topic in mathematics because of its applications. For example, a social network keeps track of users and their friendships, which helps mathematicians from all over the world stay in touch with each other and not prove the same theorem independently. It can do so by representing the situation with a graph: each vertex represents a user while there is an edge between two vertices if and only if their corresponding users are friends.

Sometimes we want to check how “dense” the graph is. One way to evaluate it is to compare the number of cliques or independent sets of a fixed size. A sparse graph has few large cliques but a lot of edges, whereas a dense graph has more larger cliques than smaller cliques. One special case of this problem is to count the number of independent sets in a tree.

\noindent \textbf{Conjecture 1}. {(Alavi, Malde, Schwenk, and Erd\H{o}s)1 The independence polynomial of every tree is unimodal.

As of now, this is still an open problem. They attempted this problem by investigating other properties of the polynomials.

\noindent \textit{Theorem 1}. (Alavi, Malde, Schwenk, and Erd\H{o}s)1 If a unimodal polynomial P\left(x\right) has positive coefficients, then for any positive real t, \left(x\mathrm{+}t\right)P\left(x\right) is also unimodal.

\noindent \textbf{Corollary 1}. \textit{If all roots of } P\left(x\right) \textit{ are real and negative then } P\left(x\right) \textit{ is unimodal.}

\noindent \textbf{Definition 1}. A spider tree is a tree in which only one vertex has degree greater than 2.

\noindent \textbf{Definition 2}. The central vertex of a spider tree is the vertex with degree greater than 2.

A more intuitive way to think about it is as follows: define a \textit{leg} of a spider tree T to be a path in T where one endpoint is the central vertex of T and the other end is a leaf of T. Then each edge in T is in exactly one leg.

This paper studies special spider trees in depth. This paper proves the following theorems:

\noindent \textit{Theorem 2}. Let T be a spider tree with m\mathrm{+}k legs, k of which have length two and m of which has length three.

  • If k\mathrm{\le }m then I\left(T\mathrm{;}x\right) is unimodal. Furthermore, \frac{I\left(T\mathrm{;}x\right)}{{\left(2x\mathrm{+}1\right)}^k} has mode m.
  • If k\mathrm{>}m and k\mathrm{\equiv }m\left(\ \mathrm{mod}\ \ 3\right) then if \frac{I\left(T\mathrm{;}x\right)}{{\left(2x\mathrm{+}1\right)}^m} is unimodal, then it has mode at most \frac{m\mathrm{+}2k}{3}

\noindent \textit{Theorem 3}. {\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m{\left(2x\mathrm{+}1\right)}^{3l} has mode m\mathrm{+}2l if {\left(x\mathrm{+}1\right)}^{2m}{\left(2x\mathrm{+}1\right)}^{3l} has mode m\mathrm{+}2l

\noindent \textit{Theorem 4}. {\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m{\left(2x\mathrm{+}1\right)}^{3l} has mode at most m\mathrm{+}2l for all l

Spider Tree

We will define \textit{Pseudo-Fibonacci Polynomials} in the following way

\noindent(F_0\left(x\right)\mathrm{=}1,F_1\left(x\right)\mathrm{=}1\mathrm{+}x), for all n\mathrm{\ge }2 ,

\noindent( F_n\left(x\right)\mathrm{=}F_{n\mathrm{-}1}\left(x\right)\mathrm{+}xF_{n\mathrm{-}2}\left(x\right)).

Note F_n\left(x\right) is the independence polynomial of a line tree with n vertices.

\noindent \textit{Proposition 1}. Suppose a spider tree T has legs of l_1,\mathrm{\cdots },l_k\mathrm{\ge}1 edges. Then its independence polynomial is

    \begin{equation}$$I\left(T\mathrm{;}x\right)\mathrm{=}\prod^k_{j\mathrm{=}1}{F_{l_j}}\left(x\right)\mathrm{+}x\prod^k_{j\mathrm{=}1}{F_{l_j\mathrm{-}1}}\left(x\right)$$\end{equation}

\textit{Proof.} We consider whether the central vertex is inside the independent set or not.

Case 1: The central vertex is not in the independent set. Consider the forest T\mathrm{'} obtained by removing the central vertex and all edges incident to it. (In other words, T\mathrm{'} is the induced subgraph of all non-central vertices) Then T\mathrm{'} is the disjoint union of k line trees (legs) of lengths l_1\mathrm{,}\mathrm{\cdots }\mathrm{,}l_k. Let P_j denote the jth leg.Then

    \[I\left(T\mathrm{'}\mathrm{;}x\right)\mathrm{=}I\left(P_1\mathrm{\bigoplus }P_2\mathrm{\bigoplus }\mathrm{\cdots }\mathrm{\bigoplus }P_k\mathrm{;}x\right)\mathrm{=}\prod^k_{j\mathrm{=}1}{I}\left(P_j\mathrm{;}x\right)\mathrm{=}\prod^k_{j\mathrm{=}1}{F_{l_j}}\left(x\right)\]

Where G\mathrm{\bigoplus }H denotes the graph sum of G,H.

Case 2: the central vertex is in the independent set. Then the neighbours of the central vertex cannot be selected. Let T\mathrm{''} be the forest obtained by the induced subgraph of all vertices except for the central vertex and its neighbours. Similar to the above argument,

    \[I\left(T\mathrm{''}\mathrm{;}x\right)\mathrm{=}\prod^k_{j\mathrm{=}1}{F_{l_j\mathrm{-}1}}\left(x\right)\]


An independent set that has the central vertex is simply the disjoint union of the central vertex and an independent set of T\mathrm{''}. Combining the two cases,

    \[I\left(T\mathrm{;}x\right)\mathrm{=}I\left(T\mathrm{'}\mathrm{;}x\right)\mathrm{+}xI\left(T\mathrm{''}\mathrm{;}x\right)\mathrm{=}\prod^k_{j\mathrm{=}1}{F_{l_j}}\left(x\right)\mathrm{+}x\prod^k_{j\mathrm{=}1}{F_{l_j\mathrm{-}}}\left(x\right)\]

, as needed.

Levit and Mandrescu2 proved that when l_1\mathrm{=}\mathrm{1,\ }l_2\mathrm{=}\mathrm{\cdots }\mathrm{=}l_k\mathrm{=}2, the polynomial is unimodal. A general piece of intuition is that the coefficient contribution of x{\left(1\mathrm{+}x\right)}^k is so negligible to that of {\left(1\mathrm{+}2x\right)}^k that the mode of x{\left(1\mathrm{+}x\right)}^k\mathrm{+}{\left(1\mathrm{+}2x\right)}^k is the same as that of {\left(1\mathrm{+}2x\right)}^k.

We will work on the case l_1,l_2\mathrm{,}\mathrm{\cdots }\mathrm{,}l_k\mathrm{\le }3.

Methods

The general insight is that the contribution of x\prod^k_{j\mathrm{=}1}{F_{l_j\mathrm{-}1}}\left(x\right) to the coefficients is negligible compared to that of \prod^k_{j\mathrm{=}1}{F_{l_j}}\left(x\right).

We will discuss methods that are employed to prove a polynomial is unimodal as well as methods that are specifically targeted towards solving this problem. We know that the coefficients of F_3{\left(x\right)}^k\mathrm{=}{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^k don’t have a closed form. However, we just need to compare sizes of coefficients. We employ a series of approaches:

  1. \item \textbf{Flattening the polynomial}: Replace {\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^k with {\left(x^2\mathrm{+}2x\mathrm{+}1\right)}^k and see if the polynomial is unimodal. This polynomial is just {\left(x\mathrm{+}1\right)}^{2k} and its coefficients are binomial coefficients.
  2. \item \textbf{Recursion}: We know the coefficients of a polynomial satisfy a certain closed form. They sometimes give a good starting place to do some recursion.
  3. \item \textbf{Knowing a polynomial is unimodal and finding the mode}: The sum of 2 unimodal polynomials with the same mode is a unimodal polynomial with the same mode.

We first resolve a special case: T is a tree with all legs of length three.
l_1\mathrm{=}l_2\mathrm{=}\mathrm{\cdots }\mathrm{=}l_k\mathrm{=}3

By Proposition 1, since T is a spider tree with all legs having length 3,

    \[I\left(T\mathrm{;}x\right)\mathrm{=}F_3{\left(x\right)}^k\mathrm{+}xF_2{\left(x\right)}^k\mathrm{=}{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^k\mathrm{+}x{\left(2x\mathrm{+}1\right)}^k\]

\noindent\textit{Theorem 5}. If k\mathrm{>}100 then this polynomial is unimodal, with mode k.

The idea is to write this polynomial as a sum of some unimodal polynomials with mode k.

We prove two lemmas.

\noindent \textit{Lemma 1}. For all k\mathrm{\ge }2, the independence polynomial Q\left(x\right)\mathrm{=}{\left(x^2\mathrm{+}2x\mathrm{+}1\right)}^k\mathrm{+}x{\left(2x\mathrm{+}1\right)}^k is unimodal with mode at k.

Proof: Note Q\left(x\right)\mathrm{=}{\left(x\mathrm{+}1\right)}^{2k}\mathrm{+}x{\left(2x\mathrm{+}1\right)}^k. For convenience of notation, \left[x^t\right]Q\left(x\right) denotes the x^t-coefficient of Q\left(x\right). Here,

    \[[x^t]Q\left(x\right)]\]

    \[-[x^t]{(x+1)}^{2k}+[x^t]x{(2x+1)}^k\]

    \[-\left(\genfrac{}{}{0pt}{}{2k}{t}\right)+[x^{t-1}]{(2x+1)}^k\]

    \[-\left(\genfrac{}{}{0pt}{}{2k}{t}\right)+\left(\genfrac{}{}{0pt}{}{k}{t-1}\right)2^{t-1}\]

{\left(x\mathrm{+}1\right)}^{2k} is unimodal with mode at k and for k\mathrm{\ge }2 we have k2^{k\mathrm{-}1}\mathrm{\ge }2^k.

Therefore,

    \[\left[x^{k\mathrm{+}1}\right]\left({\left(x^2\mathrm{+}2x\mathrm{+}1\right)}^k\mathrm{+}x{\left(2x\mathrm{+}1\right)}^k\right)\mathrm{=}\left(\genfrac{}{}{0pt}{}{2k}{k\mathrm{+}1}\right)\mathrm{+}2^k\]

    \[\mathrm{\le }\left(\genfrac{}{}{0pt}{}{2k}{k}\right)\mathrm{+}k2^{k\mathrm{-}1}\]

    \[\mathrm{-}\left[x^k\right]\left({\left(x^2\mathrm{+}2x\mathrm{+}1\right)}^k\mathrm{+}x{\left(2x\mathrm{+}1\right)}^k\right)\]

It remains to show that \left[x^k\right]P\left(x\right)\mathrm{>}\left[x^{k\mathrm{-}1}\right]P\left(x\right)\mathrm{>}\mathrm{\cdots }\mathrm{>}\left[x\right]P\left(x\right)

In other words, for all n\mathrm{\le }k, we wish to show

    \[\left(\genfrac{}{}{0pt}{}{2k}{n}\right)\mathrm{+}\left(\genfrac{}{}{0pt}{}{k}{n\mathrm{-}1}\right)2^{n\mathrm{-}1}\mathrm{>}\left(\genfrac{}{}{0pt}{}{2k}{n\mathrm{-}1}\right)\mathrm{+}\left(\genfrac{}{}{0pt}{}{k}{n\mathrm{-}2}\right)2^{n\mathrm{-}2}\]

Or

    \[\left(\genfrac{}{}{0pt}{}{2k}{n}\right)\mathrm{-}\left(\genfrac{}{}{0pt}{}{2k}{n\mathrm{-}1}\right)\mathrm{>}2^{n\mathrm{-}2}\left(\left(\genfrac{}{}{0pt}{}{k}{n\mathrm{-}2}\right)\mathrm{-}2\left(\genfrac{}{}{0pt}{}{k}{n\mathrm{-}1}\right)\right)\]

Expanding everything, we want to show

    \[\frac{\left(2k\right)\mathrm{!}}{n\mathrm{!}\left(2k\mathrm{-}n\right)\mathrm{!}}\mathrm{-}\frac{\left(2k\right)\mathrm{!}}{\left(n\mathrm{-}1\right)\mathrm{!}\left(2k\mathrm{-}n\mathrm{+}1\right)\mathrm{!}}\mathrm{>}2^{n\mathrm{-}2}\]

    \[\left(\frac{k\mathrm{!}}{\left(n\mathrm{-}2\right)\mathrm{!}\left(k\mathrm{-}n\mathrm{+}2\right)\mathrm{!}}\mathrm{-}\frac{2\mathrm{\cdot }k\mathrm{!}}{\left(n\mathrm{-}1\right)\mathrm{!}\left(k\mathrm{-}n\mathrm{+}1\right)\mathrm{!}}\right)\\]

Factoring, this is equivalent to

    \[\frac{\left(2k\right)\mathrm{!}\left(2k\mathrm{-}n\mathrm{+}1\right)}{n\mathrm{!}\left(2k\mathrm{-}n\mathrm{+}1\right)\mathrm{!}}\mathrm{-}\frac{\left(2k\right)\mathrm{!}n}{n\mathrm{!}\left(2k\mathrm{-}n\mathrm{+}1\right)\mathrm{!}}\mathrm{>}2^{n\mathrm{-}2}\]

    \[\left(\frac{k\mathrm{!}\left(n\mathrm{-}1\right)}{\left(n\mathrm{-}1\right)\mathrm{!}\left(k\mathrm{-}n\mathrm{+}2\right)\mathrm{!}}\mathrm{-}\frac{k\mathrm{!}\mathrm{\cdot }2\left(k\mathrm{-}n\mathrm{+}2\right)}{\left(n\mathrm{-}1\right)\mathrm{!}\left(k\mathrm{-}n\mathrm{+}2\right)\mathrm{!}}\right)\]

    \[\frac{\left(2k\right)\mathrm{!}}{n\mathrm{!}\left(2k\mathrm{-}n\mathrm{+}1\right)\mathrm{!}}\left(2k\mathrm{-}2n\mathrm{+}1\right)\mathrm{>}2^{n\mathrm{-}2}\]

    \[\frac{k\mathrm{!}}{\left(n\mathrm{-}1\right)\mathrm{!}\left(k\mathrm{-}n\mathrm{+}2\right)\mathrm{!}}\left(3n\mathrm{-}2k\mathrm{-}5\right)\]

    \[\frac{\left(2k\right)\mathrm{!}}{n\left(2k\mathrm{-}n\mathrm{+}1\right)\mathrm{!}}\left(2k\mathrm{-}2n\mathrm{+}1\right)\mathrm{>}2^{n\mathrm{-}2}\frac{k\mathrm{!}}{\left(k\mathrm{-}n\mathrm{+}2\right)\mathrm{!}}\left(3n\mathrm{-}2k\mathrm{-}5\right)\]

Dividing both sides by 2k,

    \[\frac{\left(2k\mathrm{-}1\right)\mathrm{!}}{n\left(2k\mathrm{-}n\mathrm{+}1\right)\mathrm{!}}\left(2k\mathrm{-}2n\mathrm{+}1\right)\mathrm{>}2^{n\mathrm{-}3}\frac{\left(k\mathrm{-}1\right)\mathrm{!}}{\left(k\mathrm{-}n\mathrm{+}2\right)\mathrm{!}}\left(3n\mathrm{-}2k\mathrm{-}5\right)\]

    \[\left(2k\mathrm{-}2n\mathrm{+}1\right)\prod^{2k\mathrm{-}1}<em>{j\mathrm{=}2k\mathrm{-}n\mathrm{+}2}{j}\mathrm{>}\left(3n\mathrm{-}2k\mathrm{-}5\right)n2^{n\mathrm{-}3}\prod^{k\mathrm{-}1}</em>{j\mathrm{=}k\mathrm{-}n\mathrm{+}3}{j}\]

If 3n\mathrm{-}2k\mathrm{-}5\mathrm{<}0 we are trivially done.

Otherwise, note 3n\mathrm{-}2k\mathrm{-}5\mathrm{\le }k\mathrm{-}5 and n\mathrm{\ge}\frac{2k\mathrm{+}5}{3}.

We will show that for all large k\mathrm{>}100,n\mathrm{\ge }\frac{2k}{3},

    \[\prod^{2k\mathrm{-}1}<em>{j\mathrm{=}2k\mathrm{-}n\mathrm{+}2}{j}\mathrm{>}\left(k\mathrm{-}5\right)k\prod^{k\mathrm{-}1}</em>{j\mathrm{=}k\mathrm{-}n\mathrm{+}3}{\left(2j\right)},\]

which proves the theorem because

    \[\left(2k\mathrm{-}2n\mathrm{+}1\right)\prod^{2k\mathrm{-}1}<em>{j\mathrm{=}2k\mathrm{-}n\mathrm{+}2}{j}\mathrm{\ge }\prod^{2k\mathrm{-}1}</em>{j\mathrm{=}2k\mathrm{-}n\mathrm{+}2}{j}\mathrm{>}\left(k\mathrm{-}5\right)k\prod^{k\mathrm{-}1}_{j\mathrm{=}k\mathrm{-}n\mathrm{+}3}\]

    \[{\left(2j\right)}\mathrm{>}\left(3n\mathrm{-}2k\mathrm{-}5\right)n2^{n\mathrm{-}3}\prod^{k\mathrm{-}1}_{j\mathrm{=}k\mathrm{-}n\mathrm{+}3}{j}\]

We cancel even terms on both sides. Now RHS is left with even terms in \mathrm{[}2\left(k\mathrm{-}n\mathrm{+}3\right),2k\mathrm{-}n\mathrm{+}2\mathrm{)} and each term in the product in the LHS is greater than each term in product the RHS. It remains to show their quotient is greater than k\left(k\mathrm{-}5\right) for all sufficiently large k. Recall n\mathrm{\ge }\frac{2k}{3}

We pair terms in the following manner: since 2\left(k\mathrm{-}n\mathrm{+}3\right)\mathrm{,}\mathrm{\cdots }\mathrm{,}2\left(\mathrm{\lfloor }\frac{k}{2}\mathrm{\rfloor }\mathrm{-}1\right) appears in RHS, we pair them with terms at least twice as large in the LHS, namely the same number of consecutive odd numbers ending with 2k\mathrm{-}1. Thus,

    \[\frac{\prod^{2k\mathrm{-}1}<em>{j\mathrm{=}2k\mathrm{-}n\mathrm{+}2}{j}}{\prod^{k\mathrm{-}1}</em>{j\mathrm{=}k\mathrm{-}n\mathrm{+}3}{\left(2j\right)}}\mathrm{\ge }\prod^{\mathrm{\lfloor }\frac{k}{2}\mathrm{\rfloor }\mathrm{-}1}<em>{j\mathrm{=}k\mathrm{-}n\mathrm{+}3}{\frac{2j\mathrm{+}k}{2j}}\mathrm{\cdot }\prod</em>{\mathrm{\lfloor }\frac{k}{2}\mathrm{\rfloor }\mathrm{\le }j\mathrm{\le }\frac{2k\mathrm{-}n\mathrm{+}1}{2}}{1}\mathrm{\ge }2^{\frac{k}{6}}\mathrm{\ge }k\left(k\mathrm{-}5\right)\]

for all k\mathrm{>}100.

Therefore, Q\left(x\right)\mathrm{=}{\left(x\mathrm{+}1\right)}^{2k}\mathrm{+}x{\left(2x\mathrm{+}1\right)}^k is unimodal.

To prove the unimodality of {\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^k\mathrm{+}x{\left(2x\mathrm{+}1\right)}^k, it remains to show that for 1\mathrm{\le }n\mathrm{\le }k,

    \[\left[x^n\right]{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^k\mathrm{-}\left[x^{n\mathrm{-}1}\right]{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^k\mathrm{>}\left[x^n\right]{\left(x^2\mathrm{+}2x\mathrm{+}1\right)}^k\]

    \[\mathrm{-}\left[x^{n\mathrm{-}1}\right]{\left(x^2\mathrm{+}2x\mathrm{+}1\right)}^k\]

Rearranging,

    \[\left[x^n\right]\left({\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^k\mathrm{-}{\left(x^2\mathrm{+}2x\mathrm{+}1\right)}^k\right)\mathrm{>}\left[x^{n\mathrm{-}1}\right]\big({\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^k\]

    \[\mathrm{-}{\left(x^2\mathrm{+}2x\mathrm{+}1\right)}^k\big)\]

This means it suffices to prove {\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^k\mathrm{-}{\left(x^2\mathrm{+}2x\mathrm{+}1\right)}^k is unimodal, with mode at k.

Consider the identity

    \[a^k\mathrm{-}b^k\mathrm{=}\left(a\mathrm{-}b\right)\left(\sum^{k\mathrm{-}1}_{j\mathrm{=}0}{a^j}b^{k\mathrm{-}1\mathrm{-}j}\right)\]

Substituting a\mathrm{=}x^2\mathrm{+}3x\mathrm{+}1,b\mathrm{=}x^2\mathrm{+}2x\mathrm{+}1, this is simply

    \[F\left(x\right)\mathrm{=}x\left(\sum^k_{j\mathrm{=}0}{{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^j}{\left(x^2\mathrm{+}2x\mathrm{+}1\right)}^{k\mathrm{-}1\mathrm{-}j}\right)\]

Call a polynomial symmetric if P\left(x\right)\mathrm{=}x^{\mathrm{deg}P}P\left(\frac{1}{x}\right). Then a,b are both symmetric. I claim F\left(x\right) is unimodal with mode k. To see this, we prove the following lemma:

\noindent \textit{Lemma 2}. If P,Q are symmetric unimodal polynomials with nonnegative coefficients such that \mathrm{deg}P\mathrm{=}2n,\mathrm{\ }\mathrm{deg}Q\mathrm{=}2m for positive integers m,n, P has mode at n and Q has mode at m, then PQ is a unimodal polynomial with mode at m\mathrm{+}n.

\noindent \textit{Proof of Lemma.} The basic idea is to use polynomials that are symmetric and easy to work with and write P\left(x\right)Q\left(x\right) as a sum of unimodal polynomials with mode m\mathrm{+}n.

Write

    \[P\left(x\right) & \mathrm{=}a_n\left(x^{2n}\mathrm{+}x^{2n\mathrm{-}1}\mathrm{+}\mathrm{\cdots }\mathrm{+}x\mathrm{+}1\right)\]

    \[& \mathrm{+}a_{n\mathrm{-}1}\left(x^{2n\mathrm{-}1}\mathrm{+}x^{2n\mathrm{-}2}\mathrm{+}\mathrm{\cdots }\mathrm{+}x\right)\]

    \[& \mathrm{+}a_{n\mathrm{-}2}\left(x^{2n\mathrm{-}2}\mathrm{+}x^{2n\mathrm{-}3}\mathrm{+}\mathrm{\cdots }\mathrm{+}x^2\right)\]

    \[& \mathrm{+}\mathrm{\cdots }\]

    \[& \mathrm{+}a_0x^n\]

Since P\left(x\right) is unimodal, a_n,a_{n\mathrm{-}1}\mathrm{,}\mathrm{\cdots }\mathrm{,}a_0 are all nonnegative.

Similarly, write

    \[Q\left(x\right) & \mathrm{=}b_m\left(x^{2m}\mathrm{+}x^{2m\mathrm{-}1}\mathrm{+}\mathrm{\cdots }\mathrm{+}x\mathrm{+}1\right)\]

    \[& \mathrm{+}b_{m\mathrm{-}1}\left(x^{2m\mathrm{-}1}\mathrm{+}x^{2m\mathrm{-}2}\mathrm{+}\mathrm{\cdots }\mathrm{+}x\right)\]

    \[& \mathrm{+}b_{m\mathrm{-}2}\left(x^{2m\mathrm{-}2}\mathrm{+}x^{2m\mathrm{-}3}\mathrm{+}\mathrm{\cdots }\mathrm{+}x^2\right)\]

    \[& \mathrm{+}\mathrm{\cdots }\]

    \[& \mathrm{+}b_0x^m\]

Where b_m\mathrm{,}\mathrm{\cdots }\mathrm{,}b_0 are nonnegative reals.

We will show that \left(x^{m\mathrm{+}t}\mathrm{+}x^{m\mathrm{+}t\mathrm{-}1}\mathrm{+}\mathrm{\cdots }\mathrm{+}x^{m\mathrm{-}t}\right) \big(x^{n\mathrm{+}s}\mathrm{+} x^{n\mathrm{+}s\mathrm{-}1}\mathrm{+}\mathrm{\cdots }\mathrm{+}x^{n\mathrm{-}s}\big) is unimodal with mode n\mathrm{+}m, which proves the theorem because

    \[P\left(x\right)Q\left(x\right)\mathrm{=}\sum_{0\mathrm{\le }s\mathrm{\le }n,0\mathrm{\le }t\mathrm{\le }m}{a_s}b_t\left(x^{n\mathrm{+}s}\mathrm{+}x^{n\mathrm{+}s\mathrm{-}1}\mathrm{+}\mathrm{\cdots }\mathrm{+}x^{n\mathrm{-}s}\right)\]

    \[\left(x^{m\mathrm{+}t}\mathrm{+}x^{m\mathrm{+}t\mathrm{-}1}\mathrm{+}\mathrm{\cdots }\mathrm{+}x^{m\mathrm{-}t}\right)\]

Since a_sb_t is nonnegative, PQ can be written as the sum of unimodal polynomials with mode n\mathrm{+}m, so PQ also has mode n\mathrm{+}m.

Note

    \[\left(x^{n\mathrm{+}s}\mathrm{+}x^{n\mathrm{+}s\mathrm{-}1}\mathrm{+}\mathrm{\cdots }\mathrm{+}x^{n\mathrm{-}s}\right)\left(x^{m\mathrm{+}t}\mathrm{+}x^{m\mathrm{+}t\mathrm{-}1}\mathrm{+}\mathrm{\cdots }\mathrm{+}x^{m\mathrm{-}t}\right)\]

    \[\mathrm{=}x^{n\mathrm{+}m}\left(x^s\mathrm{+}x^{s\mathrm{-}1}\mathrm{+}\mathrm{\cdots }\mathrm{+}x^{\mathrm{-}s}\right)\left(x^t\mathrm{+}x^{t\mathrm{-}1}\mathrm{+}\mathrm{\cdots }\mathrm{+}x^{\mathrm{-}t}\right)\]

Note \left[x^a\right]\left(x^s\mathrm{+}x^{s\mathrm{-}1}\mathrm{+}\mathrm{\cdots }\mathrm{+}x^{\mathrm{-}s}\right)\left(x^t\mathrm{+}x^{t\mathrm{-}1}\mathrm{+}\mathrm{\cdots }\mathrm{+}x^{\mathrm{-}t}\right) is the number of solutions to p\mathrm{+}q\mathrm{=}a where p\mathrm{\in }\left[\mathrm{-}s,s\right] and q\mathrm{\in }\left[\mathrm{-}t,t\right].

WLOG, s\mathrm{\ge }t and a\mathrm{\ge }0 since the number of solutions to p\mathrm{+}q\mathrm{=}a and p\mathrm{+}q\mathrm{=-}a are the same.

We have that the set of possible p is continuous. p_{max}\left(a\right)\mathrm{=min}\mathrm{{}s,a\mathrm{+}t} and p_{min}\left(a\right)\mathrm{=max}\mathrm{{}\mathrm{-}s,a\mathrm{-}t}. There are \mathrm{max}\left(0,p_{max}\left(a\right)\mathrm{-}p_{min}\left(a\right)\mathrm{+}1\right) solutions, i.e. the x^a-coefficient is \mathrm{max}\left(0,p_{max}\left(a\right)\mathrm{-}p_{min}\left(a\right)\mathrm{+}1\right)

Since s\mathrm{\ge }t, \mathrm{-}s\mathrm{\le }\mathrm{-}t\mathrm{\le }a\mathrm{-}t so p_{min}\mathrm{=}a\mathrm{-}t.

We have two cases on the size of a.

Case 1:

    \[s\mathrm{\ge }a\mathrm{+}t\]

then a\mathrm{\le }s\mathrm{-}t.

In this case we have

    \[p_{max}\left(a\right)\mathrm{-}p_{min}\left(a\right)\mathrm{+}1\mathrm{=}\left(a\mathrm{+}t\right)\mathrm{-}\left(a\mathrm{-}t\right)\mathrm{+}1\mathrm{=}2t\mathrm{+}1\]

Case 2:

    \[s\mathrm{>}a\mathrm{+}t\]

then we have,

    \[p_{max}\left(a\right)\mathrm{-}p_{min}\left(a\right)\mathrm{+}1\mathrm{=}s\mathrm{-}\left(a\mathrm{-}t\right)\mathrm{+}1\mathrm{=}\left(s\mathrm{+}t\mathrm{+}1\right)\mathrm{-}a\]

which is decreasing as a increases. When a\mathrm{=}s\mathrm{-}t\mathrm{-}1, this value is 2t.

In short, the x^a coefficient is 2t\mathrm{+}1 if 0\mathrm{\le }a\mathrm{\le }s\mathrm{-}t and s\mathrm{+}t\mathrm{+}1\mathrm{-}a when a\mathrm{>}s\mathrm{-}t. Therefore,

    \[\left(x^{m\mathrm{+}t}\mathrm{+}x^{m\mathrm{+}t\mathrm{-}1}\mathrm{+}\mathrm{\cdots }\mathrm{+}x^{m\mathrm{-}t}\right)\left(x^{n\mathrm{+}s}\mathrm{+}x^{n\mathrm{+}s\mathrm{-}1}\mathrm{+}\mathrm{\cdots }\mathrm{+}x^{n\mathrm{-}s}\right)\]

is unimodal with mode n\mathrm{+}m, proving lemma 2.

\noindent \textit{Proof of Theorem 5.}

By Lemma 2, {\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^j{\left(x^2\mathrm{+}2x\mathrm{+}1\right)}^{k\mathrm{-}1\mathrm{-}j} has mode k\mathrm{-}1 for all 0\mathrm{\le }j\mathrm{\le }k\mathrm{-}1.

Therefore,

    \[{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^k\mathrm{+}x{\left(2x\mathrm{+}1\right)}^k\mathrm{=}\left({\left(x\mathrm{+}1\right)}^{2k}\mathrm{+}x{\left(2x\mathrm{+}1\right)}^k\right)\mathrm{+}\]

    \[x\sum^{k\mathrm{-}1}_{j\mathrm{=}0}{{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^j}{\left(x^2\mathrm{+}2x\mathrm{+}1\right)}^{k\mathrm{-}1\mathrm{-}j}\]

By lemmas 1 and 2, each polynomial in the summation is a polynomial with mode k, so {\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^k\mathrm{+}x{\left(2x\mathrm{+}1\right)}^k is a unimodal polynomial with mode k.

{\boldsymbol{l}}_{\boldsymbol{j}}\boldsymbol{\mathrm{\in }}\boldsymbol{\mathrm{{}}\boldsymbol{2},\boldsymbol{3}}

Suppose the spider tree T has m legs of length 3 and k legs of length 2.

By Proposition 1,

    \[I\left(T,x\right)\mathrm{=}{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m{\left(2x\mathrm{+}1\right)}^k\mathrm{+}x{\left(2x\mathrm{+}1\right)}^m{\left(x\mathrm{+}1\right)}^k\\]

We have 2 cases.

\boldsymbol{k}\boldsymbol{\mathrm{\le }}\boldsymbol{m}

We shall prove Theorem 2 (i): I\left(T\mathrm{;}x\right) is unimodal and \frac{I\left(T\mathrm{;}x\right)}{{\left(2x\mathrm{+}1\right)}^k} has mode m.

    \[I\left(T,x\right)\mathrm{=}{\left(2x\mathrm{+}1\right)}^k\left({\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m\mathrm{+}x{\left(2x\mathrm{+}1\right)}^{m\mathrm{-}k}{\left(x\mathrm{+}1\right)}^k\right)\]

By Theorem 1, \frac{I\left(T\mathrm{;}x\right)}{{\left(2x\mathrm{+}1\right)}^k} unimodal implies I\left(T\mathrm{;}x\right) unimodal.

We will use recursion: we call a unimodal polynomial P\left(x\right) \textit{very smooth} if its mode is m and for all 0\mathrm{\le }d_1\mathrm{<}d_2, \left[x^{m\mathrm{\pm }d_2}\right]P\left(x\right)\mathrm{\le }\left[x^{m\mathrm{\pm }d_1}\right]P\left(x\right), where \left[x^a\right]P\left(x\right)\mathrm{=}0 if a\mathrm{>deg}P or a\mathrm{<}0.

Since {\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m is symmetric and unimodal, it is very smooth.

We induct on m to first show that {\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m\mathrm{+}x{\left(2x\mathrm{+}1\right)}^m is very smooth.

Note

    \[\left[x^{m\mathrm{+}d}\right]\left({\left(x^2\mathrm{+}3m\mathrm{+}1\right)}^m\mathrm{+}x{\left(2x\mathrm{+}1\right)}^m\right)\]

    \[\mathrm{=}\left[x^{m-d}\right]{\left(x^2\mathrm{+}3m\mathrm{+}1\right)}^m\mathrm{+}\left[x^{m+d}\right]\left(x{\left(2x\mathrm{+}1\right)}^m\right)\]

    \[\mathrm{\le }\left[x^{m-d}\right]\left({\left(x^2\mathrm{+}3m\mathrm{+}1\right)}^m\mathrm{+}x{\left(2x\mathrm{+}1\right)}^m\right)\]

Therefore, it suffices to prove for all d\mathrm{\ge }0,

    \[\left[x^{m\mathrm{+}d}\right]\left({\left(x^2\mathrm{+}3m\mathrm{+}1\right)}^m\mathrm{+}x{\left(2x\mathrm{+}1\right)}^m\right)\mathrm{\ge }\left[x^{m\mathrm{+}d}\right]{\left(x^2\mathrm{+}3m\mathrm{+}1\right)}^m\]

    \[\mathrm{\ge }\left[x^{m\mathrm{-}d\mathrm{-}1}\right]\left({\left(x^2\mathrm{+}3m\mathrm{+}1\right)}^m\mathrm{+}x{\left(2x\mathrm{+}1\right)}^m\right)\]

We have

    \[\left[x^n\right]x{\left(2x\mathrm{+}1\right)}^m\mathrm{=}\left[x^{n\mathrm{-}1}\right]{\left(2x\mathrm{+}1\right)}^m\mathrm{=}2^{n\mathrm{-}1}\left(\genfrac{}{}{0pt}{}{m}{n\mathrm{-}1}\right)\]

Let

    \[f\left(m,n\right)\mathrm{=}\left[x^n\right]{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m\]

and Q\left(m,d\right) denote the assertion

    \[left[x^{m\mathrm{+}d}\right]{\left(x^2\mathrm{+}3m\mathrm{+}1\right)}^m\mathrm{\ge }\left[x^{m\mathrm{-}d\mathrm{-}1}\right]\left({\left(x^2\mathrm{+}3m\mathrm{+}1\right)}^m\mathrm{+}x{\left(2x\mathrm{+}1\right)}^m\right)\]

or in short,

    \[Q\left(m,d\right)\mathrm{:}f\left(m,m\mathrm{-}d\right)\mathrm{=}f\left(m,m\mathrm{+}d\right)\mathrm{\ge }f\left(m,m\mathrm{-}\left(d\mathrm{+}1\right)\right)\]

    \[\mathrm{+}2^{m\mathrm{-}d\mathrm{-}2}\left(\genfrac{}{}{0pt}{}{m}{m\mathrm{-}d\mathrm{-}2}\right)\]

The base cases, m\mathrm{\le }7 can be verified by hand.

Inductive step: Note f satisfies the recursion

    \[f\left(m,n\right)\mathrm{=}f\left(m\mathrm{-}1,n\right)\mathrm{+}3f\left(m\mathrm{-}1,n\mathrm{-}1\right)\mathrm{+}f\left(m\mathrm{-}1,n\mathrm{-}2\right)\]

Case 1: d\mathrm{=}0.

We have,

    \[f\left(m,m\right)\mathrm{-}f\left(m,m\mathrm{-}1\right)& \mathrm{=}f\left(m\mathrm{-}1,m\right)\mathrm{+}3f\left(m\mathrm{-}1,m\mathrm{-}1\right)\mathrm{+}\]

    \[& f\left(m\mathrm{-}1,m\mathrm{-}2\right)\mathrm{-}f\left(m\mathrm{-}1,m\mathrm{-}1\right)\mathrm{-}\]

    \[& 3f\left(m\mathrm{-}1,m\mathrm{-}2\right)\mathrm{-}f\left(m\mathrm{-}1,m\mathrm{-}3\right)\]

Since

    \[ <!-- /wp:paragraph --> <!-- wp:paragraph --> f\left(m\mathrm{-}1,m\right)& \mathrm{=}\left[x^m\right]{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^{m\mathrm{-}1}\]

    \[& \mathrm{=}\left[x^{m\mathrm{-}2}\right]{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^{m\mathrm{-}1}\]

    \[& \mathrm{=}f\left(m\mathrm{-}1,m\mathrm{-}2\right)\]

by symmetry, it follows that

    \[f\left(m,m\right)\mathrm{-}f\left(m,m\mathrm{-}1\right) \mathrm{=}2f\left(m\mathrm{-}1,m\mathrm{-}2\right)\mathrm{+}3f\left(m\mathrm{-}1,m\mathrm{-}1\right)\mathrm{-}\]

    \[f\left(m\mathrm{-}1,m\mathrm{-}1\right)\mathrm{-}3f\left(m\mathrm{-}1,m\mathrm{-}2\right)\mathrm{-}f\left(m\mathrm{-}1,m\mathrm{-}3\right)\]

    \[\mathrm{=}2f\left(m\mathrm{-}1,m\mathrm{-}1\right)\mathrm{-}f\left(m\mathrm{-}1,m\mathrm{-}2\right)\mathrm{-}&f\left(m\mathrm{-}1,m\mathrm{-}3\right)\]

    \[\mathrm{=}2\left(f\left(m\mathrm{-}1,m\mathrm{-}1\right)\mathrm{-}f\left(m\mathrm{-}1,m\mathrm{-}2\right)\right)&\mathrm{+}\big(f\left(m\mathrm{-}1,m\mathrm{-}2\right)\]

    \[&\mathrm{-}f\left(m\mathrm{-}1,m\mathrm{-}3\right)\big)\]

By Q\left(m\mathrm{-}1,0\right),Q\left(m\mathrm{-}1,1\right), we have

    \[2\left(f\left(m\mathrm{-}1,m\mathrm{-}1\right)\mathrm{-}f\left(m\mathrm{-}1,m\mathrm{-}2\right)\right)\mathrm{+}\big(f\left(m\mathrm{-}1,m\mathrm{-}2\right)\]

    \[mathrm{-}f\left(m\mathrm{-}1,m\mathrm{-}3\right)\big)\]

    \[& \mathrm{\ge }2^{m\mathrm{-}2}\left(\genfrac{}{}{0pt}{}{m\mathrm{-}1}{2}\right)\mathrm{+}2^{m\mathrm{-}4}\left(\genfrac{}{}{0pt}{}{m\mathrm{-}1}{3}\right)\]

    \[& \mathrm{\ge }2^{m\mathrm{-}2}\left(\genfrac{}{}{0pt}{}{m}{2}\right)\]

,For all m\mathrm{\ge }8.

Now, we note

    \[{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m\mathrm{+}x{\left(2x\mathrm{+}1\right)}^{m\mathrm{-}k}{\left(x\mathrm{+}1\right)}^k\]

is very smooth because,

    \[\left[x^{m\mathrm{+}d}\right]{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m\mathrm{\ge}\left[x^{m\mathrm{-}d\mathrm{-}1}\right]{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m\mathrm{+}x\left(2x\mathrm{+}1\right)\]

Case 2: d\mathrm{=}m\mathrm{-}2

We have f\left(m,1\right)\mathrm{=}3m because

    \[\left[x\right]{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m\mathrm{=}\left[x\right]{\left(3x\mathrm{+}1\right)}^m\]

Also,

    \[f\left(m,2\right)\mathrm{=}9\left(\genfrac{}{}{0pt}{}{m}{2}\right)\mathrm{+}m\]

because I either pick one x^2 and m\mathrm{-}1 1\mathrm{'}s or I select two 3x and m\mathrm{-}2 1\mathrm{'}s.

We have

    \[f\left(m,m\mathrm{-}\left(m\mathrm{-}2\right)\right)\mathrm{-}f\left(m,m\mathrm{-}\left(m\mathrm{-}1\right)\right)\mathrm{=}\9\left(\genfrac{}{}{0pt}{}{m}{2}\right)\mathrm{-}2m\mathrm{>}1\mathrm{=}2^{m\mathrm{-}\left(m\mathrm{-}2\right)\mathrm{-}2}\left(\genfrac{}{}{0pt}{}{m}{m\mathrm{-}\left(m\mathrm{-}2\right)\mathrm{-}2}\right)\]

if m\mathrm{\ge }8

Case 3: 0\mathrm{<}d\mathrm{\le }m\mathrm{-}3.

Then

    \[& f\left(m,m\mathrm{-}d\right)\mathrm{-}f\left(m,m\mathrm{-}d\mathrm{-}1\right)\]

    \[& \mathrm{=}f\left(m\mathrm{-}1,m\mathrm{-}d\right)\mathrm{+}3f\left(m\mathrm{-}1,m\mathrm{-}1\mathrm{-}d\right)\mathrm{+}f\left(m\mathrm{-}1,m\mathrm{-}2\mathrm{-}d\right)\mathrm{-}\]

    \[& f\left(m\mathrm{-}1,m\mathrm{-}1\mathrm{-}d\right)\mathrm{-}3f\left(m\mathrm{-}1,m\mathrm{-}2\mathrm{-}d\right)\mathrm{-}f\left(m\mathrm{-}1,m\mathrm{-}3\mathrm{-}d\right)\]

    \[& \mathrm{=}f\left(m\mathrm{-}1,m\mathrm{-}d\right)\mathrm{-}f\left(m\mathrm{-}1,m\mathrm{-}d\mathrm{-}1\right)\mathrm{+}3\big(f\left(m\mathrm{-}1,m\mathrm{-}d\mathrm{-}1\right)\]

    \[&\mathrm{-}f\left(m\mathrm{-}1,m\mathrm{-}d\mathrm{-}2\right)\big)\mathrm{+}f\left(m\mathrm{-}1,m\mathrm{-}d\mathrm{-}2\right)\mathrm{-}f\left(m\mathrm{-}1,m\mathrm{-}d\mathrm{-}3\right)\]

By

    \[Q\left(m\mathrm{-}1,d\mathrm{-}1\right),Q\left(m\mathrm{-}1,d\right)\]

we have this is at least

    \[2^{m\mathrm{-}d\mathrm{-}2}\left(\genfrac{}{}{0pt}{}{m\mathrm{-}1}{m\mathrm{-}d\mathrm{-}2}\right)\mathrm{+}3\mathrm{\cdot }2^{m\mathrm{-}d\mathrm{-}3}\left(\genfrac{}{}{0pt}{}{m\mathrm{-}1}{m\mathrm{-}d\mathrm{-}3}\right)\mathrm{\ge }2^{m\mathrm{-}d\mathrm{-}2}\]

    \[\left(\left(\genfrac{}{}{0pt}{}{m\mathrm{-}1}{m\mathrm{-}d\mathrm{-}2}\right)\mathrm{+}\left(\genfrac{}{}{0pt}{}{m\mathrm{-}1}{m\mathrm{-}d\mathrm{-}3}\right)\right)\mathrm{=}2^{m\mathrm{-}d\mathrm{-}2}\left(\genfrac{}{}{0pt}{}{m}{m\mathrm{-}d\mathrm{-}2}\right)\]

Having exhausted all cases, the induction is complete.

Now I’ll prove that {\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m\mathrm{+}x{\left(2x\mathrm{+}1\right)}^{m\mathrm{-}k}{\left(x\mathrm{+}1\right)}^k is very smooth with mode m. Observe

    \[\left[x^{m\mathrm{\pm }d}\right]\left({\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m\mathrm{+}x{\left(2x\mathrm{+}1\right)}^{m\mathrm{-}k}{\left(x\mathrm{+}1\right)}^k\right)\]

    \[\mathrm{\ge }\left[x^{m\mathrm{\pm }d}\right]{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m\]

By Q\left(m,d\right),

    \[\left[x^{m\mathrm{\pm }d}\right]{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m\mathrm{\ge }\left[x^{m\mathrm{\pm}\mathrm{(}d+1)}\right]\left({\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m\mathrm{+}x{\left(2x\mathrm{+}1\right)}^m\right)\]

    \[\mathrm{\ge }\left[x^{m\mathrm{\pm }\mathrm{(}d+1)}\right]\left({\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m\mathrm{+}x{\left(2x\mathrm{+}1\right)}^{m\mathrm{-}k}{\left(x\mathrm{+}1\right)}^k\right)\]

\noindent \textit{Remark 1}. This is an alternative method to deal with the case l_1\mathrm{=}l_2\mathrm{=}\mathrm{\cdots }\mathrm{=}l_k\mathrm{=}3, i.e. to show {\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m\mathrm{+}x{\left(2x\mathrm{+}1\right)}^m is unimodal with mode m.

\boldsymbol{k}\boldsymbol{\mathrm{>}}\boldsymbol{m},\boldsymbol{k}\boldsymbol{\mathrm{\equiv }}\boldsymbol{m}\left(\boldsymbol{\ }\mathrm{mod}\boldsymbol{\ }\boldsymbol{\ }\boldsymbol{3}\right)

The independence polynomial is still

    \[I\left(T\mathrm{;}x\right)\mathrm{=}{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m{\left(2x\mathrm{+}1\right)}^k\mathrm{+}x{\left(2x\mathrm{+}1\right)}^m{\left(x\mathrm{+}1\right)}^k\]

Write k\mathrm{=}m\mathrm{+}n.

\noindent \textit{Proof of Theorem 2 (ii).}

Since n\mathrm{=}k\mathrm{-}m\mathrm{\equiv }0\left(\ \mathrm{mod}\ \ 3\right), n\mathrm{=}3l

for some integer l. It suffices to show the mode of

    \[\frac{I\left(T\mathrm{;}x\right)}{{\left(2x\mathrm{+}1\right)}^m}\mathrm{=}{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m{\left(2x\mathrm{+}1\right)}^n\mathrm{+}x{\left(x\mathrm{+}1\right)}^{m\mathrm{+}n}\]

is at most m\mathrm{+}2l.

\noindent \textit{Lemma 3}.

For all integers d,

    \[\left[x^{m\mathrm{+}2l\mathrm{+}d\mathrm{+}1}\right]\left({\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m{\left(2x\mathrm{+}1\right)}^n\mathrm{+}x{\left(x\mathrm{+}1\right)}^{m\mathrm{+}n}\right)\]

    \[\mathrm{\le }\left[x^{m\mathrm{+}2l\mathrm{-}d}\right]\left({\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m{\left(2x\mathrm{+}1\right)}^n\mathrm{+}x{\left(x\mathrm{+}1\right)}^{m\mathrm{+}n}\right)\]

\noindent\textit{Proof of Lemma 3.}

Fix l. Let

    \[f\left(m,t\right)\mathrm{=}\left[x^t\right]{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m{\left(2x\mathrm{+}1\right)}^{3l}\]

Observe the recursion,

    \[f\left(m,t\right)\mathrm{=}f\left(m\mathrm{-}1,t\right)\mathrm{+}3f\left(m\mathrm{-}1,t\mathrm{-}1\right)\mathrm{+}f\left(m\mathrm{-}1,t\mathrm{-}2\right)\]

Rewrite,

    \[\frac{I\left(T\mathrm{;}x\right)}{{\left(2x\mathrm{+}1\right)}^m}\mathrm{=}{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m{\left(1\mathrm{+}2x\right)}^{3l}\mathrm{+}x{\left(x\mathrm{+}1\right)}^{m\mathrm{+}3l}\]

We are able to prove a modified version of the base case, where m\mathrm{=}0: for all 0\mathrm{\le }t\mathrm{<}l,

    \[\left[x^{2l\mathrm{-}t}\right]{\left(2x\mathrm{+}1\right)}^{3l}\mathrm{>}\left[x^{2l\mathrm{+}t\mathrm{+}1}\right]{\left(2x\mathrm{+}1\right)}^{3l}\]

To prove the base case of m\mathrm{=}0, we do a smaller induction on t.

Base Case: t\mathrm{=}0.

We need to show,

    \[2^{2l}\left(\genfrac{}{}{0pt}{}{3l}{2l}\right)\mathrm{>}2^{2l\mathrm{+}1}\left(\genfrac{}{}{0pt}{}{3l}{2l\mathrm{+}1}\right)\]

This is true because

    \[\frac{2^{2l}\left(\genfrac{}{}{0pt}{}{3l}{2l}\right)}{2^{2l\mathrm{+}1}\left(\genfrac{}{}{0pt}{}{3l}{2l\mathrm{+}1}\right)}\mathrm{=}\frac{\left(2l\mathrm{+}1\right)\mathrm{!}\left(l\mathrm{-}1\right)\mathrm{!}}{2\left(2l\right)\mathrm{!}l\mathrm{!}}\mathrm{=}\frac{2l\mathrm{+}1}{2l}\mathrm{>}1\]

Inductive Step: Assume

    \[2^{2l\mathrm{-}t}\left(\genfrac{}{}{0pt}{}{3l}{2l\mathrm{-}t}\right)\mathrm{>}2^{2l\mathrm{+}t\mathrm{+}1}\left(\genfrac{}{}{0pt}{}{3l}{2l\mathrm{+}t\mathrm{+}1}\right)\]

What to show:

    \[2^{2l\mathrm{-}t\mathrm{-}1}\left(\genfrac{}{}{0pt}{}{3l}{2l\mathrm{-}t\mathrm{-}1}\right)\mathrm{>}2^{2l\mathrm{+}t\mathrm{+}2}\left(\genfrac{}{}{0pt}{}{3l}{2l\mathrm{+}t\mathrm{+}2}\right)\]

It suffices to show

    \[\frac{2^{2l\mathrm{-}t\mathrm{-}1}\left(\genfrac{}{}{0pt}{}{3l}{2l\mathrm{-}t\mathrm{-}1}\right)}{2^{2l\mathrm{-}t}\left(\genfrac{}{}{0pt}{}{3l}{2l\mathrm{-}t}\right)}\mathrm{>}\frac{2^{2l\mathrm{+}t\mathrm{+}2}\left(\genfrac{}{}{0pt}{}{3l}{2l\mathrm{+}t\mathrm{+}2}\right)}{2^{2l\mathrm{+}t\mathrm{+}1}\left(\genfrac{}{}{0pt}{}{3l}{2l\mathrm{+}t\mathrm{+}1}\right)}\]

Expanding, the inequality becomes

    \[\frac{2l\mathrm{-}t}{l\mathrm{+}t\mathrm{+}1}\mathrm{>}4\frac{l\mathrm{-}t\mathrm{-}1}{2l\mathrm{+}t\mathrm{+}2}\]

    \[\mathrm{\Leftrightarrow }\frac{2l\mathrm{-}t}{2l\mathrm{+}2t\mathrm{+}2}\mathrm{>}\frac{2l\mathrm{-}2t\mathrm{-}2}{2l\mathrm{+}t\mathrm{+}2}\]

    \[\mathrm{\Leftrightarrow }\left(2l\mathrm{-}t\right)\left(2l\mathrm{+}t\mathrm{+}2\right)\mathrm{>}\left(2l\mathrm{+}2t\mathrm{+}2\right)\left(2l\mathrm{-}2t\mathrm{-}2\right)\]

    \[\mathrm{\Leftrightarrow }{\left(2l\mathrm{+}1\right)}^2\mathrm{-}{\left(t\mathrm{+}1\right)}^2\mathrm{>}{\left(2l\right)}^2\mathrm{-}{\left(2t\mathrm{+}2\right)}^2,\]

which is clear.

This resolves the case where m\mathrm{=}0, because,

    \[\left[x^{2l\mathrm{-}t}\right]{\left(2x\mathrm{+}1\right)}^{3l}\mathrm{>}\left[x^{2l\mathrm{+}t\mathrm{+}1}\right]{\left(2x\mathrm{+}1\right)}^{3l}\]

    \[\left[x^{2l\mathrm{-}t}\right]x{\left(x\mathrm{+}1\right)}^{3l}\mathrm{>}\left[x^{2l\mathrm{+}t}\right]x{\left(x\mathrm{+}1\right)}^{3l}\]

and adding them yields the desired result.

Inductive Step: recall the recursion

    \[f\left(m,m\mathrm{+}2l\mathrm{+}d_1\right)\mathrm{=}f\left(m\mathrm{-}1,\left(m\mathrm{-}1\right)\mathrm{+}2l\mathrm{+}\left(d_1\mathrm{+}1\right)\right)\mathrm{+}3f\big(m\mathrm{-}1,\]

    \[\left(m\mathrm{-}1\right)\mathrm{+}2l\mathrm{+}d_1\big)\mathrm{+}f\left(m\mathrm{-}1,\left(m\mathrm{-}1\right)\mathrm{+}2l\mathrm{+}\left(d_1\mathrm{-}1\right)\right)\]

    \[f\left(m,m\mathrm{+}2l\mathrm{+}d_2\right)\mathrm{=}f\left(m\mathrm{-}1,\left(m\mathrm{-}1\right)\mathrm{+}2l\mathrm{+}\left(d_2\mathrm{+}1\right)\right)\mathrm{+}3f\big(m\mathrm{-}1,\]

    \[\left(m\mathrm{-}1\right)\mathrm{+}2l\mathrm{+}d_2\big)\mathrm{+}f\left(m\mathrm{-}1,\left(m\mathrm{-}1\right)\mathrm{+}2l\mathrm{+}\left(d_2\mathrm{-}1\right)\right)\]

Case 1: d_1,d_2 have the same sign with 0\mathrm{<}\left|d_1\right|\mathrm{<}\left|d_2\right|. By inductive hypothesis,

    \[f\left(m\mathrm{-}1,\left(m\mathrm{-}1\right)\mathrm{+}2l\mathrm{+}\left(d_1\mathrm{+}1\right)\right)&\mathrm{>}f\left(m\mathrm{-}1,\left(m\mathrm{-}1\right)\mathrm{+}2l\mathrm{+}\left(d_2\mathrm{+}1\right)\right)\]

    \[f\left(m\mathrm{-}1,\left(m\mathrm{-}1\right)\mathrm{+}2l\mathrm{+}d_1\right)&\mathrm{>}f\left(m\mathrm{-}1,\left(m\mathrm{-}1\right)\mathrm{+}2l\mathrm{+}d_2\right)\]

    \[f\left(m\mathrm{-}1,\left(m\mathrm{-}1\right)\mathrm{+}2l\mathrm{+}\left(d_1\mathrm{-}1\right)\right)&\mathrm{>}f\mathrm{(}m\mathrm{-}1,\left(m\mathrm{-}1\right)\mathrm{+}2l\mathrm{+}\left(\left(d_1\mathrm{-}1\right)\right)\]

So their difference is

    \[&f\left(m\mathrm{-}1,\left(m\mathrm{-}1\right)\mathrm{+}2l\mathrm{+}\left(d_1\mathrm{+}1\right)\right)\mathrm{-}f\big(m\mathrm{-}1,\left(m\mathrm{-}1\right)\mathrm{+}2l\mathrm{+}\]

    \[&\big(d_2\mathrm{+}1\big)\big)\mathrm{+}3\big(f\big(m\mathrm{-}1,\big(m\mathrm{-}1\big)\mathrm{+}2l\mathrm{+}d_1\big)\mathrm{-}f\big(m\mathrm{-}1,\big(m\mathrm{-}1\big)\mathrm{+}\]

    \[&2l\mathrm{+}d_2\big)\big)\mathrm{+}f\left(m\mathrm{-}1,\left(m\mathrm{-}1\right)\mathrm{+}2l\mathrm{+}\left(d_1\mathrm{-}1\right)\right)\mathrm{-}f\mathrm{(}m\mathrm{-}1,\left(m\mathrm{-}1\right)\mathrm{+}\]

    \[&2l\mathrm{+}\left(\left(d_1\mathrm{-}1\right)\right)\mathrm{>}0\]

If d_1d_2\mathrm{<}0 and \left|d_1\right|\mathrm{<}\left|d_2\right|, then

    \[&f\left(k,k\mathrm{+}2l\mathrm{+}d_1\right)\mathrm{-}f\left(k,k\mathrm{+}2l\mathrm{+}d_2\right)\]

    \[&\mathrm{=}f\left(k\mathrm{-}1,\left(k\mathrm{-}1\right)\mathrm{+}2l\mathrm{+}\left(d_1\mathrm{+}1\right)\right)\mathrm{-}f\left(k\mathrm{-}1,\left(k\mathrm{-}1\right)\mathrm{+}2l\mathrm{+}\left(d_2\mathrm{-}1\right)\right)\mathrm{+}\]

    \[&3\left(f\left(k\mathrm{-}1,\left(k\mathrm{-}1\right)\mathrm{+}2l\mathrm{+}d_1\right)\mathrm{-}f\left(k\mathrm{-}1,\left(k\mathrm{-}1\right)\mathrm{+}2l\mathrm{+}d_2\right)\right)\mathrm{+}f\big(k\mathrm{-}1,\]

    \[&\left(k\mathrm{-}1\big)\mathrm{+}2l\mathrm{+}\left(d_1\mathrm{-}1\right)\right)\mathrm{-}f\mathrm{(}k\mathrm{-}1,\left(k\mathrm{-}1\right)\mathrm{+}2l\mathrm{+}\left(\left(d_1\mathrm{+}1\right)\right)\mathrm{>}0\]

Since

    \[&\left[x^{m\mathrm{+}2l\mathrm{-}t}\right]x{\left(x\mathrm{+}1\right)}^{m\mathrm{+}3l}\mathrm{>}\left[x^{m\mathrm{+}2l\mathrm{+}t\mathrm{+}1}\right]x{\left(x\mathrm{+}1\right)}^{m\mathrm{+}3l},\]

    \[&\left[x^{m\mathrm{+}2l\mathrm{-}t}\right]{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m{\left(2x\mathrm{+}1\right)}^{3l}\mathrm{+}x{\left(x\mathrm{+}1\right)}^{m\mathrm{+}3l}\]

    \[&\mathrm{>}\left[x^{m\mathrm{+}2l\mathrm{+}t\mathrm{+}1}\right]{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m{\left(2x\mathrm{+}1\right)}^{3l}\mathrm{+}x{\left(x\mathrm{+}1\right)}^{m\mathrm{+}3l}\]

It follows that the mode of

    \[{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m{\left(2x\mathrm{+}1\right)}^{3l}\mathrm{+}x{\left(x\mathrm{+}1\right)}^{m\mathrm{+}3l}\]

is at most m\mathrm{+}2l, since

    \[&\left[x^{m\mathrm{+}2l\mathrm{+}t\mathrm{+}1}\right]{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m{\left(2x\mathrm{+}1\right)}^{3l}\mathrm{+}x{\left(x\mathrm{+}1\right)}^{m\mathrm{+}3l}\]

    \[&\mathrm{\le }\left[x^{m\mathrm{+}2l\mathrm{-}t}\right]{\left(x^2\mathrm{+}3x\mathrm{+}1\right)}^m{\left(2x\mathrm{+}1\right)}^{3l}\mathrm{+}x{\left(x\mathrm{+}1\right)}^{m\mathrm{+}3l}\]

for all t\mathrm{\ge }0.

Conclusion

This paper has proven a few results on the unimodality and the mode of a special type of spider trees. We have a few problems that are yet to be solved.

\noindent \textbf{Problem 1}. If k\mathrm{>}m, what happens if n\mathrm{\equiv }1\left(\ \mathrm{mod}\ \ 3\right) or n\mathrm{\equiv }2\left(\ \mathrm{mod}\ \ 3\right)?

We anticipate the mode will still be close to m\mathrm{+}2\mathrm{\lfloor }\frac{n}{3}\mathrm{\rfloor }.

\noindent \textbf{Problem 2}. Are the spider trees with l_k\mathrm{\le }4, l_k\mathrm{\le }5, or in general unimodal? Is there a convenient way to find the modes of their polynomials?

Acknowledgments

I am grateful to Mr. Andrey Khesin for being my mentor and the Lumiere program for supporting my research.

References

  1. Y. Alavi, P. J. Malde, A. J. Schwenk, P. Erd\H{o}s. The vertex independence sequence of a graph is not constrained. Eighteenth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, Fla., 1987). Congr. Numer. 58 (1987), 15–23. [↩] [↩] [↩]
  2. V. E. Levit; E. Mandrescu. On unimodality of independence polynomials of some well-covered trees. Discrete mathematics and theoretical computer science, 237–256, Lecture Notes in Comput. Sci., 2731, Springer, Berlin, 2003. [↩]

RELATED ARTICLESMORE FROM AUTHOR