A Combinatorial Proof of Bass’s Evaluations of the Ihara-Selberg Zeta Function for Graphs

Foata, Dominique; Zeilberger, Doron

doi:10.1090/S0002-9947-99-02234-5

A Combinatorial Proof of Bass’s Evaluations of the Ihara-Selberg Zeta Function for Graphs
HTML articles powered by AMS MathViewer

by Dominique Foata and Doron Zeilberger PDF

Trans. Amer. Math. Soc. 351 (1999), 2257-2274 Request permission

Abstract:

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.

References

Guido Ahumada, Fonctions périodiques et formule des traces de Selberg sur les arbres, C. R. Acad. Sci. Paris Sér. I Math. 305 (1987), no. 16, 709–712 (French, with English summary). MR 920048
S. A. Amitsur, On the characteristic polynomial of a sum of matrices, Linear and Multilinear Algebra 8 (1979/80), no. 3, 177–182. MR 560557, DOI 10.1080/03081088008817315
Hyman Bass, The Ihara-Selberg zeta function of a tree lattice, Internat. J. Math. 3 (1992), no. 6, 717–797. MR 1194071, DOI 10.1142/S0129167X92000357
P. Cartier and D. Foata, Problèmes combinatoires de commutation et réarrangements, Lecture Notes in Mathematics, No. 85, Springer-Verlag, Berlin-New York, 1969 (French). MR 0239978, DOI 10.1007/BFb0079468
K.-T. Chen, R. H. Fox, and R. C. Lyndon, Free differential calculus. IV. The quotient groups of the lower central series, Ann. of Math. (2) 68 (1958), 81–95. MR 102539, DOI 10.2307/1970044
Dominique Foata, A combinatorial proof of Jacobi’s identity, Ann. Discrete Math. 6 (1980), 125–135. MR 593527, DOI 10.1016/S0167-5060(08)70699-X
Jean-Pierre Jouanolou, Personal communication, 1996.
M. Lothaire, Combinatorics on words, Encyclopedia of Mathematics and its Applications, vol. 17, Addison-Wesley Publishing Co., Reading, Mass., 1983. A collective work by Dominique Perrin, Jean Berstel, Christian Choffrut, Robert Cori, Dominique Foata, Jean Eric Pin, Guiseppe Pirillo, Christophe Reutenauer, Marcel-P. Schützenberger, Jacques Sakarovitch and Imre Simon; With a foreword by Roger Lyndon; Edited and with a preface by Perrin. MR 675953
Percy A. MacMahon, Combinatory analysis, Chelsea Publishing Co., New York, 1960. Two volumes (bound as one). MR 0141605
Sam Northshield, Proofs of Ihara’s Theorem for Regular and Irregular Graphs, Proc. I.M.A. Workshop “Emerging Applications of Number Theory" (submitted) (1996).
Dominique Perrin, Personal communication, 1996.
Christophe Reutenauer and Marcel-Paul Schützenberger, A formula for the determinant of a sum of matrices, Lett. Math. Phys. 13 (1987), no. 4, 299–302. MR 895292, DOI 10.1007/BF00401158
Gian-Carlo Rota, On the foundations of combinatorial theory. I. Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), 340–368 (1964). MR 174487, DOI 10.1007/BF00531932
Gian-Carlo Rota, Report on the present state of combinatorics, Proceedings of the 5th Conference on Formal Power Series and Algebraic Combinatorics (Florence, 1993), 1996, pp. 289–303. MR 1394961, DOI 10.1016/0012-365X(95)00143-K
Marcel-Paul Schützenberger, Sur une propriété combinatoire des algèbres de Lie libres pouvant être utilisée dans un problème de mathématiques appliquées, Séminaire d’algèbre et de théorie des nombres [P. Dubreil, M.-L. Dubreil-Jacotin, C. Pisot, 1958-59], Secrétariat Mathématique, 11, rue Pierre-Curie, F-75005, 1960, pp. 1-01–1-13.
M. P. Schützenberger, On a factorisation of free monoids, Proc. Amer. Math. Soc. 16 (1965), 21–24. MR 170971, DOI 10.1090/S0002-9939-1965-0170971-9
Richard P. Stanley, Enumerative combinatorics. Vol. I, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1986. With a foreword by Gian-Carlo Rota. MR 847717, DOI 10.1007/978-1-4615-9763-6
H. M. Stark and A. A. Terras, Zeta functions of finite graphs and coverings, Adv. Math. 121 (1996), no. 1, 124–165. MR 1399606, DOI 10.1006/aima.1996.0050
Gérard Viennot, Algèbres de Lie libres et monoïdes libres, Lecture Notes in Mathematics, vol. 691, Springer, Berlin, 1978 (French). Bases des algèbres de Lie libres et factorisations des monoïdes libres. MR 516004, DOI 10.1007/BFb0067950
Doron Zeilberger, A combinatorial approach to matrix algebra, Discrete Math. 56 (1985), no. 1, 61–72. MR 808086, DOI 10.1016/0012-365X(85)90192-X