## 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 monotonically increases until one point , called the mode, from which it monotonically decreases afterwards as 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 , where is the size of the largest independent set in and is the number of independent sets of size in .

In 1987, Alavi, Malde, Schwenk and Erd conjectured that the independence polynomial of every tree is unimodal^{1}. 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.

. ^{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.

. ^{1} If a unimodal polynomial has positive coefficients, then for any positive real , is also unimodal.

.

. A spider tree is a tree in which only one vertex has degree greater than 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 of a spider tree to be a path in where one endpoint is the central vertex of and the other end is a leaf of . Then each edge in is in exactly one leg.

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

. Let be a spider tree with legs, of which have length two and of which has length three.

- If then is unimodal. Furthermore, has mode .
- If and then if is unimodal, then it has mode at most

. has mode if has mode

. has mode at most for all

## Spider Tree

We will define in the following way

, for all ,

.

Note is the independence polynomial of a line tree with vertices.

. Suppose a spider tree has legs of edges. Then its independence polynomial is

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 obtained by removing the central vertex and all edges incident to it. (In other words, is the induced subgraph of all non-central vertices) Then is the disjoint union of line trees (legs) of lengths . Let denote the th leg.Then

Where denotes the graph sum of .

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

An independent set that has the central vertex is simply the disjoint union of the central vertex and an independent set of . Combining the two cases,

, as needed.

Levit and Mandrescu^{2} proved that when , the polynomial is unimodal. A general piece of intuition is that the coefficient contribution of is so negligible to that of that the mode of is the same as that of .

We will work on the case

## Methods

The general insight is that the contribution of to the coefficients is negligible compared to that of .

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 don’t have a closed form. However, we just need to compare sizes of coefficients. We employ a series of approaches:

- : Replace with and see if the polynomial is unimodal. This polynomial is just and its coefficients are binomial coefficients.
- : We know the coefficients of a polynomial satisfy a certain closed form. They sometimes give a good starting place to do some recursion.
- : The sum of 2 unimodal polynomials with the same mode is a unimodal polynomial with the same mode.

We first resolve a special case: is a tree with all legs of length three.

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

. If then this polynomial is unimodal, with mode .

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

We prove two lemmas.

. For all , the independence polynomial is unimodal with mode at .

Proof: Note . For convenience of notation, denotes the -coefficient of . Here,

is unimodal with mode at and for we have .

Therefore,

It remains to show that

In other words, for all , we wish to show

Or

Expanding everything, we want to show

Factoring, this is equivalent to

Dividing both sides by ,

If we are trivially done.

Otherwise, note and .

We will show that for all large ,

which proves the theorem because

We cancel even terms on both sides. Now RHS is left with even terms in 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 for all sufficiently large . Recall

We pair terms in the following manner: since 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 . Thus,

for all .

Therefore, is unimodal.

To prove the unimodality of , it remains to show that for ,

Rearranging,

This means it suffices to prove is unimodal, with mode at .

Consider the identity

Substituting , this is simply

Call a polynomial symmetric if . Then are both symmetric. I claim is unimodal with mode . To see this, we prove the following lemma:

. If are symmetric unimodal polynomials with nonnegative coefficients such that for positive integers , has mode at and has mode at , then is a unimodal polynomial with mode at .

The basic idea is to use polynomials that are symmetric and easy to work with and write as a sum of unimodal polynomials with mode .

Write

Since is unimodal, are all nonnegative.

Similarly, write

Where are nonnegative reals.

We will show that is unimodal with mode , which proves the theorem because

Since is nonnegative, can be written as the sum of unimodal polynomials with mode , so also has mode .

Note

Note is the number of solutions to where and .

WLOG, and since the number of solutions to and are the same.

We have that the set of possible is continuous. and . There are solutions, i.e. the -coefficient is

Since , so .

We have two cases on the size of a.

Case 1:

then .

In this case we have

Case 2:

then we have,

which is decreasing as increases. When this value is .

In short, the coefficient is if and when . Therefore,

is unimodal with mode , proving lemma 2.

By Lemma 2, has mode for all .

Therefore,

By lemmas 1 and 2, each polynomial in the summation is a polynomial with mode , so is a unimodal polynomial with mode .

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

By Proposition 1,

We have 2 cases.

We shall prove Theorem 2 (i): is unimodal and has mode .

By Theorem 1, unimodal implies unimodal.

We will use recursion: we call a unimodal polynomial \textit{very smooth} if its mode is and for all , , where if or .

Since is symmetric and unimodal, it is very smooth.

We induct on to first show that is very smooth.

Note

Therefore, it suffices to prove for all ,

We have

Let

and denote the assertion

or in short,

The base cases, can be verified by hand.

Inductive step: Note satisfies the recursion

Case 1: .

We have,

Since

by symmetry, it follows that

By , we have

,For all .

Now, we note

is very smooth because,

Case 2:

We have because

Also,

because I either pick one and or I select two and .

We have

if

Case 3: .

Then

By

we have this is at least

Having exhausted all cases, the induction is complete.

Now I’ll prove that is very smooth with mode . Observe

By

. This is an alternative method to deal with the case , i.e. to show is unimodal with mode .

The independence polynomial is still

Write .

Since ,

for some integer . It suffices to show the mode of

is at most .

For all integers ,

Fix . Let

Observe the recursion,

Rewrite,

We are able to prove a modified version of the base case, where : for all ,

To prove the base case of , we do a smaller induction on .

Base Case: .

We need to show,

This is true because

Inductive Step: Assume

What to show:

It suffices to show

Expanding, the inequality becomes

which is clear.

This resolves the case where , because,

and adding them yields the desired result.

Inductive Step: recall the recursion

Case 1: have the same sign with . By inductive hypothesis,

So their difference is

If and , then

Since

It follows that the mode of

is at most , since

for all .

## 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.

. If , what happens if or ?

We anticipate the mode will still be close to .

. Are the spider trees with , , 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

- Y. Alavi, P. J. Malde, A. J. Schwenk, P. Erd. 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. [↩] [↩] [↩] - 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. [↩]