Accepted for publication in Trans. Amer. Math. Soc., 18 pages
Dominique Foata and Doron Zeilberger
A combinatorial proof of Bass's evaluations of the
Ihara-Selberg Zeta function for graphs
We derive combinatorial proofs of the main two evaluations of the Ihara-Selberg
Zeta function associated with a graph. We give three proofs of the first
evaluation all based on the algebra
of Lyndon words. In the third proof it is shown that
the first evaluation is an immediate consequence
of Amitsur's identity on the characteristic polynomial of a sum of matrices.
The second evaluation of the Ihara-Selberg Zeta function is first derived by
means of a sign-changing involution technique. Our second approach makes
use of a short matrix-algebra argument.
The following versions are available: