Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



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

Authors: Dominique Foata and Doron Zeilberger
Journal: Trans. Amer. Math. Soc. 351 (1999), 2257-2274
MSC (1991): Primary 05C05, 05C25, 05C50; Secondary 11F72, 15A15, 16A27
Published electronically: February 8, 1999
MathSciNet review: 1487614
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. 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
  • 2. 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, 10.1080/03081088008817315
  • 3. Hyman Bass, The Ihara-Selberg zeta function of a tree lattice, Internat. J. Math. 3 (1992), no. 6, 717–797. MR 1194071, 10.1142/S0129167X92000357
  • 4. 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
  • 5. 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 0102539
  • 6. Dominique Foata, A combinatorial proof of Jacobi’s identity, Ann. Discrete Math. 6 (1980), 125–135. Combinatorial mathematics, optimal designs and their applications (Proc. Sympos. Combin. Math. and Optimal Design, Colorado State Univ., Fort Collins, Colo., 1978). MR 593527
  • 7. Jean-Pierre Jouanolou, Personal communication, 1996.
  • 8. 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
  • 9. Percy A. MacMahon, Combinatory analysis, Two volumes (bound as one), Chelsea Publishing Co., New York, 1960. MR 0141605
  • 10. Sam Northshield, Proofs of Ihara's Theorem for Regular and Irregular Graphs, Proc. I.M.A. Workshop ``Emerging Applications of Number Theory" (submitted) (1996).
  • 11. Dominique Perrin, Personal communication, 1996.
  • 12. 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, 10.1007/BF00401158
  • 13. 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 0174487
  • 14. 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, 10.1016/0012-365X(95)00143-K
  • 15. 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.
  • 16. M. P. Schützenberger, On a factorisation of free monoids, Proc. Amer. Math. Soc. 16 (1965), 21–24. MR 0170971, 10.1090/S0002-9939-1965-0170971-9
  • 17. 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
  • 18. H. M. Stark and A. A. Terras, Zeta functions of finite graphs and coverings, Adv. Math. 121 (1996), no. 1, 124–165. MR 1399606, 10.1006/aima.1996.0050
  • 19. 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
  • 20. Doron Zeilberger, A combinatorial approach to matrix algebra, Discrete Math. 56 (1985), no. 1, 61–72. MR 808086, 10.1016/0012-365X(85)90192-X

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 05C05, 05C25, 05C50, 11F72, 15A15, 16A27

Retrieve articles in all journals with MSC (1991): 05C05, 05C25, 05C50, 11F72, 15A15, 16A27

Additional Information

Dominique Foata
Affiliation: Département de Mathématique, Université Louis Pasteur, 7, rue René-Descartes, F-67084 Strasbourg, France

Doron Zeilberger
Affiliation: Department of Mathematics, Temple University, Philadelphia, Pennsylvania 19122

Keywords: Ihara-Selberg zeta function, Lyndon words, Amitsur identity
Received by editor(s): March 2, 1997
Published electronically: February 8, 1999
Additional Notes: The second author was supported in part by N.S.F. and the first author as a consultant of Zeilberger on his grant.
Dedicated: This paper is dedicated to Gian-Carlo Rota, on his millionth$_{2}$’s birthday.
Article copyright: © Copyright 1999 American Mathematical Society