Ihara zeta function( 2nd part )

In this post I shall continue with some of the properties of the Ihara zeta function.
Allow me to say a bit more for the complex nature of Ihara’s zeta function. Since Ihara zeta function is function of complex variable and to be more specific a power series in the complex variable { u }, then it must have non-negative coefficients. So from the classical theorem of Landau, the product and the series defining Ihara zeta function will converge absolutely in a circle u smaller than { R_X } and will have a singularity at { u = R_X }.
For those who don’t have the time to search for Landau’s theorem, I state it here copying it from Tom Apostol’s analytic number theory book:

Theorem 1 {Landau’s theorem concerning Dirichlet series having non-negative coefficients}

Let { F(s) } be represented in the half-plane { \sigma > c } by the Dirichlet series

{F(s)= \sum_{n=1}^\infty \dfrac{f(n)}{n^s}, }

where { c } is finite, and assume that { f(n) \geq 0 } for all { n \geq n_0 }. If { F(s) } is analytic in some disk about the point { s = c }, then the Dirichlet series converges in the half-plane { \sigma > c - \epsilon } for some { \epsilon > 0 }. Consequently, if the Dirichlet series has a finite abscissa of convergence { \sigma_c }, then { F(s) } has a singularity on the real axis at points { s = \sigma_c }.

Another point I want to make, is that Ihara zeta function can determine the structure of a graph. To see this, let’s begin with the following lemma.

Lemma 2

{ Z_G(u) } determines i) if { G } is bipartite and ii) if { G } cyclic.

Before we start presenting the proof can we see why is this true? Ok let’s take a simple case where our graph is a n-cycle i.e. a cyclic graph of { n } vertices. I am sure you can all imagine that such a graph has two prime walks(one for each ‘direction’) of length { n } (you might want to draw it on a piece of paper and apply the prime walk definition). So immediately we can say that { Z_G(u) = (1 + u^n + u^{2n} \dots )^2 }. Here is a first connection, a very simple Ihara zeta function of a cyclic graph. A final thought before the proof is that a bipartite graph has a very common property concerning its closed walks(can you guess which one?) , so having in mind that Ihara zeta function is defined over prime walks (which are closed walks), we may have a connection with whether a graph is bipartite or not. Lets state now our proof.

Proof:

i) { \Rightarrow } {G } is nonbipartite, so { G } contains an odd cycle { C} which represents a prime walk of odd degree.
{ \Leftarrow } If { G } is bipartite, then every closed walk has even degree, and hence every prime walk has even degree.
Now if we consider that { Z_G(u) } is an Euler product i.e. { Z_G(u) = \prod_C ( 1 +u^{deg(C)} + u^{2deg(C)} + u^{3deg(C)} \dots ) }, we can see that { G } does not contain a prime walk of odd degree if and only if an odd power of { u } appears in the previous power series. So, to put all pieces together, { G } is not bipartite if and only if an odd power of { u } appears in the power series { Z_G(u) }. Note that from the Bass formula, { Z_G(u)^{-1} } is a polynomial so we can just look up for any odd power of { u } in { Z_G(u)^{-1} }.

ii) As we said in our remarks before our proof we can say that { G } is a { n - cycle } if and only if { Z_G(u) = ( 1+ u^n + u^{2n} \dots )^2 }.

{ \Rightarrow } It is trivial if compute the prime walks of a { n - cycle }. { \Leftarrow } If { Z_G(u) = ( 1+ u^n + u^{2n} \dots )^2 } then it has two prime walks of length { n } which implies that either { G } is { n-cycle } or { G } is a linear graph of length { n }. But as we said in our previous post our assumption that { G } has minimum degree at least 2, forces us to choose the { n-cycle } .

\Box

Note: A linear graph is a graph with the form of a line, i.e { n + 1 } vertices connected by { n } edges in this way: { u_1 } to { u_2}, {u_2} to { u_3 } , { \dots } , { u_n } to { u_{n+1} }.

Now lets state the following theorem.

Theorem 3

Suppose that { G } is connected graph with minimum degree at least 2. Let { d } be the number of times { 1 - u^2 } divides { det(I-Au-Qu^2) }. Then

{ d = \begin{cases} 0 & \text{if G is nonbipartite} \\ 1 & \text{if G is bipartite but not an 2n cycle} \\ 2 & \text{if G is a 2n cycle} \end{cases} }

Exercise: Prove the following theorem:

Theorem 4

Let { G } be a connected graph with minimal degree at least 3. Then it can be determined from the Ihara zeta function whether { G } is
i) not bipartite
ii) bipartite but not cyclic, or
iii) bipartite and cyclic,
and in these cases the vertex number { n } of { G } is given by
i) { n = e - \delta }
ii) { n = e - \delta + 1 }
iii) { n = e - \delta + 2 }
where { \delta } is the number of times { 1 - u^2 } divides { Z_G(u)^{-1} } and { e } is the number of edges of { G }.

Hint: Use the previous theorem and lemma.

The references remain the same as in my previous post, but I would like to motivate you to explore the book Zeta functions of Graphs, a Stroll through the Garden by Audrey Terras and of course this book here by Reinhard Diestel which will strongly accompany you to your explorations in graduate level graph theory.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: