Zeta Functions of Graphs: A Stroll through the GardenGraph theory meets number theory in this stimulating book. Ihara zeta functions of finite graphs are reciprocals of polynomials, sometimes in several variables. Analogies abound with number-theoretic functions such as Riemann/Dedekind zeta functions. For example, there is a Riemann hypothesis (which may be false) and prime number theorem for graphs. Explicit constructions of graph coverings use Galois theory to generalize Cayley and Schreier graphs. Then non-isomorphic simple graphs with the same zeta are produced, showing you cannot hear the shape of a graph. The spectra of matrices such as the adjacency and edge adjacency matrices of a graph are essential to the plot of this book, which makes connections with quantum chaos and random matrix theory, plus expander/Ramanujan graphs of interest in computer science. Created for beginning graduate students, the book will also appeal to researchers. Many well-chosen illustrations and exercises, both theoretical and computer-based, are included throughout. |
Contents
II Ihara zeta function and the graph theory prime number theorem | 43 |
III Edge and path zeta functions | 81 |
IV Finite unramified Galois coverings of connected graphs | 103 |
V Last look at the garden | 209 |
Common terms and phrases
adjacency matrix algebraic number analog Artin L-functions backtrackless base graph Cayley graph circle conjecture conjugacy class corresponding cosets covering graphs cube cycle Dedekind zeta function defined Definition density det(I determinant formula directed edge edge adjacency matrix edge L-function edge zeta function eigenvalues entries example Exercise Figure follows Frobenius automorphism fundamental group Galois group Galois theory graph coverings graph theory group G H₁ Hoory Ihara zeta function intermediate cover intermediate graphs intermediate to Y/X irreducible isomorphic isospectral k-regular LE(W Lemma length level spacings lift loops Lubotzky Math normal cover normalized Frobenius automorphism number fields number theory permutation prime number theorem proof Proposition prove quadratic cover radius Ramanujan graphs random regular graphs Riemann hypothesis Sarnak Selberg sheet Siegel pole spanning tree spectrum Terras tetrahedron unramified usual hypotheses vector W₁ Y/X is normal zeros