What Are Zeta Functions of Graphs and What Are They Good For?

IAS/PRINCETON NUMBER THEORY SEMINAR
Topic:What Are Zeta Functions of Graphs and What Are They Good For?
Speaker:Audrey Terras
Affiliation:University of California, San Diego
Date:Wednesday, November 9
Time/Room:2:00pm - 3:00pm/Fine Hall 314

I will discuss relatively new kinds of zeta and L-functions - the Ihara-Selberg-Artin L-functions attached to finite graph coverings. In joint work with Harold Stark, we have found that many of the methods used by number theorists in investigations of the Dedekind zeta function of algebraic number fields (and its analogue for function fields) can be applied to give graph theoretic results. Examples of applications are: 1) to obtain analogues of the prime number theorem for cycles in graphs; 2) to find examples of graphs which are connected, without loops and multiple edges and which are isospectral but not isomorphic; 3) to study the behavior of cycles and their lifts to covering graphs and analogues of the Tchebotarev density theorem; 4) For connected (q+1)-regular graphs (i.e., such that each vertex has (q+1) edges coming out), the analogue of the Riemann hypothesis for the Ihara-Selberg zeta function is true if and only if the graph is Ramanujan in the sense of Lubotzky, Phillips and Sarnak. That is, the non-trivial part of the spectrum of the adjacency matrix of the graph is bounded by that of its universal covering tree - the interval (2q^(-1/2); 2q^(-1/2)). Ramanujan graphs make efficient communications networks but examples are not easily found. The first were obtained by Lubotzky, Phillips and Sarnak and independently by Margulies; 5) to give analogues of Selberg's trace formula for irregular graphs. One question we will consider is: What happens to application 4) above when the graph is not regular?