|
A Combinatorial Proof of Bass's Evaluations of the Ihara-Selberg Zeta Function for Graphs
Author(s):
Dominique
Foata;
Doron
Zeilberger
Journal:
Trans. Amer. Math. Soc.
351
(1999),
2257-2274.
MSC (1991):
Primary 05C05, 05C25, 05C50;
Secondary 11F72, 15A15, 16A27
Posted:
February 8, 1999
Retrieve article in:
PDF
This article is available free of charge
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:
- 1.
- Guido Ahumada, Fonctions périodiques et formule des traces de Selberg sur les arbres, C. R. Acad. Sci. Paris 305 (1987), 709-712. MR 89d:11103
- 2.
- S. A. Amitsur, On the Characteristic Polynomial of a Sum of Matrices, Linear and Multilinear Algebra 9 (1980), 177-182. MR 82a:15014
- 3.
- Hyman Bass, The Ihara-Selberg Zeta Function of a Tree Lattice, Internat. J. Math. 3 (1992), 717-797. MR 94a:11072
- 4.
- Pierre Cartier and Dominique Foata, Problèmes combinatoires de commutation et réarrangements, Springer-Verlag (Lecture Notes in Math., vol. 85), Berlin, 1969. MR 39:1332
- 5.
- K.T. Chen, R.H. Fox and R.C. Lyndon, Free differential calculus, IV. The quotient groups of the lower central series, Ann. Math. 68 (1958), 81-95. MR 21:1330
- 6.
- Dominique Foata, A combinatorial proof of Jacobi's identity, Ann. Discrete Math. 6 (1980), 125-135. MR 83c:05003
- 7.
- Jean-Pierre Jouanolou, Personal communication, 1996.
- 8.
- M. Lothaire, Combinatorics on Words, Addison-Wesley (Encyclopedia of Math. and its Appl., vol. 17), Reading, Mass., 1983. MR 84g:05002
- 9.
- (Major) P.A. MacMahon, Combinatory Analysis, vol. 1, Cambridge Univ. Press (Reprinted by Chelsea, New York, 1955), Cambridge, 1915. MR 25:5003
- 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, Letters of Math. Physics 13 (1987), 299-302. MR 88d:15010
- 13.
- Gian-Carlo Rota, On the Foundations of Combinatorial Theory. I Theory of Möbius Function, Z. Wahrscheinlichkeitstheorie 2 (1964), 340-368. MR 30:4688
- 14.
- Gian-Carlo Rota, Report on the present state of combinatorics (Inaugural address delivered at the 5th Formal Power Series and Algebraic Combinatorics Conference, Florence, 21 June 1993), Discrete Math. 153 (1996), 289-303. MR 97k:05001
- 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.
- Marcel-Paul Schützenberger, On a factorization of free monoids, Proc. Amer. Math. Soc. 16 (1965), 21-24. MR 30:1205
- 17.
- Richard P. Stanley, Enumerative Combinatorics, vol. 1, Wadsworth & Brooks, Monterey, 1986. MR 87j:05003
- 18.
- H. M. Stark and A. A. Terras, Zeta Functions of Finite Graphs and Coverings, Adv. in Math. 121 (1996), 124-165. MR 98b:11094
- 19.
- Gérard Viennot, Algèbres de Lie libres et monoïdes libres, Springer-Verlag (Lecture Notes in Math., vol. 691), Berlin, 1978. MR 80i:17016
- 20.
- Doron Zeilberger, A Combinatorial Approach to Matrix Algebra, Discrete Math. 56 (1985), 61-72. MR 87b:05016
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
Email:
foata@math.u-strasbg.fr
Doron
Zeilberger
Affiliation:
Department of Mathematics, Temple University, Philadelphia, Pennsylvania 19122
Email:
zeilberg@math.temple.edu
DOI:
10.1090/S0002-9947-99-02234-5
PII:
S 0002-9947(99)02234-5
Keywords:
Ihara-Selberg zeta function,
Lyndon words,
Amitsur identity
Received by editor(s):
March 2, 1997
Posted:
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.
Copyright of article:
Copyright
1999,
American Mathematical Society
|
Comments: webmaster@ams.org