1
$\begingroup$

This sounds like a simple piece of math (which got a long story over time, thanks for reading!) and the consequence seems surprising. At least to me. Here it is:

It boils down to comparing two expression of the reciprocal/inverse of the Ihara zeta function $\frac{1}{\zeta_G(u)}$ for planar graphs and compare the resulting polynomials: $$ \prod_{p} ({1 - u^{L(p)}}) \overset{!}{=}{(1-u^2)^{\chi(G)-1}\det(I - Au + (k-1)u^2I)} $$


The Wiki page on the Ihara $\zeta$ function of a graph $G$ with $n$ vertices gives two definitions:

  1. $$ \frac{1}{\zeta_G(u)} = \prod_{p} ({1 - u^{L(p)}}) \tag{1} $$ This product is taken over all prime walks $p$ of the graph $G = (V, E)$... $L(p)$ is the length of cycle $p$ (i.e. prime walks on $G$).
  2. If we restrict ourselves to $k$-regular graphs, we also have: $$ \frac{1}{\zeta_G(u)} = {(1-u^2)^{\chi(G)-1}\det(I - Au + (k-1)u^2I)} \tag{2}$$ where $χ$ is the circuit rank, which is the number of edges deleted from $G$ to form a spanning tree and alternativley,the rank of the fundamental group of the graph.

Let's compare the degree of the polynomials in $u$ in both expressions.

We can use $\chi=F-1$, for planar graphs. $F$ is the number of faces. So $(1-u^2)^{F-2}$ has degree $2(\color{red}{F-2})$.

Now the determinant in the latter expression can be written as product over the eigenvaues $\lambda_m$ of the adjacency matrix $A$: $$ P_A(u)=\prod_{m=1}^n (1-\lambda_mu+(k-1)u^2) \tag{3} $$ This gives a degree of $2\color{blue}n$. A more compact form for cubic graphs is given below...


So the total degree is $2(\color{blue}n+\color{red}{F-2})$. If we apply Euler formula for planar graphs we get $2E$, twice the number of edges. Therefore we have: $$\sum_p L(p)=2E. \tag{4}$$

This is also stated here: The coefficients of the Ihara zeta function, p.219 and seems to have an easy explanation: All prime walks are faces and contribute each edge twice.

But then this means: All Ihara $\zeta$ functions for planar $k$-regular graphs with a given set of faces are equivalent, irrespective of their actual arrangement and although their spectra of $A$ might differ...

Is this correct?


It is true that there are references that state that there are infinitely many prime walks $p$ and then the above said, doesn't make sense. Maybe I got something wrong, so I would be glad if you could point out my error...

EDIT sorry, the numerics looked strange, I gotta think about it...

EDIT2: If we assume $k$-regular graphs, we set $u=(k-1)^{-s}=q^{-s}$ (see The Riemann hypothesis for graphs), this simplifies to $$ q^{-ns}\prod_{m=1}^n ((q^s+q^{1-s})-\lambda_m ) \tag{3$^*$} $$ which further simplifies for $k$-regular Ramanujan graphs, i.e. $\lambda_1\leq 2\sqrt{k-1}$, since the Riemann hypothesis holds (see proof in link) on this case and $s=1/2+ib$, therefore $q^s+q^{1-s}=2\sqrt q \cos(b \log q)$

$\endgroup$
  • 1
    $\begingroup$ For a regular graph, the characteristic polynomial of its adjacency matrix and its zeta function give the same information. $\endgroup$ – Chris Godsil Dec 15 '15 at 0:42
2
+50
$\begingroup$

Like Chris Godsil says in the comments, for regular graphs, the Ihara zeta function contains the same information as the (multi)set of eigenvalues of the adjacency matrix. So two $k$-regular graphs have the same Ihara zeta function iff they're isospectral.

$\endgroup$
  • 1
    $\begingroup$ @draks: there are only finitely many prime walks of a certain length, so the product converges in the $u$-adic topology. Here's an example of such an infinite product converging to a rational function: qchu.wordpress.com/2009/11/03/… $\endgroup$ – Qiaochu Yuan Dec 22 '15 at 19:24
  • 1
    $\begingroup$ @draks... I don't have much intelligent to add, but you can try the following experiment to convince yourself that an infinite product can equal a polynomial. Consider the 4-regular graph with one vertex and two loops. This graph has $A=\begin{bmatrix}4\end{bmatrix}$ and has three faces, so $$\frac{1}{\zeta_G(u)}=(1-u^2)(1-4u+3u^2).$$ With some work, one finds that the numbers of equivalence classes of primitive, nonbacktracking circuits of lengths 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... are 4, 4, 8, 18, 48, 116, 312, 810, 2184, 5880, 16104, ... Evaluating the product ... $\endgroup$ – Will Orrick Dec 23 '15 at 6:13
  • 1
    $\begingroup$ $$\begin{aligned}&(1-u)^4(1-u^2)^4(1-u^3)^8(1-u^4)^{18}(1-u^5)^{48}(1-u^6)^{116}(1-u^7)^{312}\\ &\quad\times(1-u^8)^{810}(1-u^9)^{2184}(1-u^{10})^{5880}(1-u^{11})^{16104}\ ,\end{aligned}$$ one finds that it equals $(1-u^2)(1-4u+3u^2)+O(u^{12})$. The exponents are computed as follows: label one of the loops $1$ and the other $2$. The loops may be traversed in either direction, so we arbitrarily choose one of the directions on each loop to be the forward direction, and denote the reverse directions $\bar{1}$ and $\bar{2}$. Two circuits, written as words ... $\endgroup$ – Will Orrick Dec 23 '15 at 6:25
  • 1
    $\begingroup$ ... on the alphabet $\{1,\bar{1},2,\bar{2}\}$, are equivalent if they are cyclic shifts of each other. A word is nonprimitive if it equals a nonzero cyclic shift of itself. To be nonbacktracking, the letters $1$ and $\bar{1}$ may not be adjacent, with a similar restriction on the letters $2$ and $\bar{2}$. So the circuits of length $1$ are $1$, $\bar{1}$, $2$, $\bar{2}$, and the circuits of length $2$ are $12$, $1\bar{2}$, $\bar{1}2$, $\bar{1}\bar{2}$. $\endgroup$ – Will Orrick Dec 23 '15 at 6:25
  • 1
    $\begingroup$ @draks... I have not verified anything, but $(1-u^2)(1-4u+3u^3)$ has zeroes at $-1$, $1$, and $\frac{1}{3}$, so I expect that the product converges in the usual power-series sense to $\left[\zeta(u)\right]^{-1}$ for $\lvert u\rvert<\frac{1}{3}$. The "$u$-adic topology" presumably means that two polynomials are considered to be close when their difference is proportional to a high power of $u$. My expectation is that the product converges to $(1-u^2)(1-4u+3u^3)$ in the sense that their difference is proportional to arbitrarily high powers of $u$ as the number of factors goes to infinity. $\endgroup$ – Will Orrick Dec 23 '15 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.