Counting Paths in Graphs

By Laurent Bartholdi. 2000

134 citations recorded by the source corpus.

We give a simple combinatorial proof of a formula that extends a result by Grigorchuk (rediscovered by Cohen) relating cogrowth and spectral radius of random walks. Our main result is an explicit equation determining the number of `bumps' on paths in a graph: in a $d$-regular (not necessarily transitive) non-oriented graph let the series $G(t)$ count all paths between two fixed points weighted by their length $t^{length}$, and $F(u,t)$ count the same paths, weighted as $u^{number of bumps}t^{length}$. Then one has $$F(1-u,t)/(1-u^2t^2) = G(t/(1+u(d-u)t^2))/(1+u(d-u)t^2).$$ We then derive the circuit series of `free products' and `direct products' of graphs. We also obtain a generalized form of the Ihara-Selberg zeta function.

Subfields: Computational Theory and Mathematics, Geometry and Topology, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/c56c3ee95ffc4d4dc407b3309b42a0f10e2918f6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Geometry and Topology

In Statistics and Probability

Citations in the corpus

Expansion of random graphs: new proofs, new results (2012, unknown): “[7,8,48], but see limitations in [51]).”
THE NON-BACKTRACKING SPECTRUM OF THE UNIVERSAL COVER OF A GRAPH (2007, background): “In that context, the number of non-backtracking walks is asymptotically given by the cogrowth of the graph (see [7, 18, 27, 33]).”
Probability on Trees and Networks (2017, methodology): “See Bartholdi (1999) for a relationship between the numbers of cycles of different lengths at a vertex and the numbers of cycles of different lengths with given numbers of backtracking edge pairs. His analysis extends that of the generating functions used in Section 6.3. Our proof of Theorem 6.11 is”
The measurable Kesten theorem (2011, background): “but may equal +1. Rewriting our bound in terms of C we get EV A2 104z1 nC0(z) + 500 1(o2A): MEASURABLE KESTEN 21 Let G(z) be the analogous generating function for simple random walk. It was shown in [5], (see formula (2.3) in [27]) that for any d-regular graph we have C(z) = 1(o2A) d + (d 1)2 z2 d(d”