A Brouwer fixed-point theorem for graph endomorphisms

We prove a Lefschetz formula L(T)=∑x∈FiT(x) for graph endomorphisms T:G→G, where G is a general finite simple graph and ℱ is the set of simplices fixed by T. The degree iT(x) of T at the simplex x is defined as (−1)dim(x)sign(T|x), a graded sign of the permutation of T restricted to the simplex. The Lefschetz number L(T) is defined similarly as in the continuum as L(T)=∑k(−1)ktr(Tk), where Tk is the map induced on the k th cohomology group Hk(G) of G. The theorem can be seen as a generalization of the Nowakowski-Rival fixed-edge theorem (Nowakowski and Rival in J. Graph Theory 3:339-350, 1979). A special case is the identity map T, where the formula reduces to the Euler-Poincaré formula equating the Euler characteristic with the cohomological Euler characteristic. The theorem assures that if L(T) is nonzero, then T has a fixed clique. A special case is the discrete Brouwer fixed-point theorem for graphs: if T is a graph endomorphism of a connected graph G, which is star-shaped in the sense that only the zeroth cohomology group is nontrivial, like for connected trees or triangularizations of star shaped Euclidean domains, then there is clique x which is fixed by T. If A is the automorphism group of a graph, we look at the average Lefschetz number L(G). We prove that this is the Euler characteristic of the chain G/A and especially an integer. We also show that as a consequence of the Lefschetz formula, the zeta function ζT(z)=exp(∑n=1∞L(Tn)znn) is a product of two dynamical zeta functions and, therefore, has an analytic continuation as a rational function. This explicitly computable product formula involves the dimension and the signature of prime orbits.MSC:58J20, 47H10, 37C25, 05C80, 05C82, 05C10, 90B15, 57M15, 55M20.