Open problems related to adjacency eigenvalues and zeta functions

We express some open problems in graph theory in terms of Ihara graph zeta
functions, or, equivalently, non-backtracking matrices of graphs.  We focus
on "expanders" and random regular graphs, but touch on some seemingly
unrelated problems encoded in zeta functions.

We suggest that zeta functions of sheaves on graphs may have relevance to
complexity theory and to questions of Stark and Terras regarding whether
coverings of a fixed graph can ramify like number field extensions.

This talk assumes only basic linear algebra and graph theory.  Part of the
material is joint work with David Kohler and Doron Puder.