# Growth rate of number of loops in a graph

Let G be a directed graph with a countable number of vertices, and suppose G is strongly connected (given any two vertices v and w, there exists a path from v to w). Fix a base vertex v0∈G, and let Ln denote the number of loops of length n based at v0; that is, the number of sequences of vertices v0, v1, ..., vn such that vn = v0 and there is an edge from vi to vi+1 for every 0 ≤ i < n. We allow the loops to self-intersect, repeat segments, etc.

Let h be the exponential growth rate of the number of such loops: $h=\lim_{n\to\infty} \frac 1n \log L_n$. The value of h may be either finite or infinite, and I am interested in finding conditions on the graph that help determine which of these is the case.

Question: Is there any characterisation of the set of graphs for which h < ∞? A necessary and sufficient condition would be ideal, but anything that is known would be appreciated.

Partial answer so far: If G is uniformly locally finite -- that is, if there exists C < ∞ such that every vertex of G has incoming degree ≤ C or every vertex has outgoing degree ≤ C -- then Ln ≤ Cn, and so h ≤ log(C) < ∞. However, it is not difficult to construct locally finite graphs with unbounded degree, or even graphs that are not locally finite, for which h < ∞, so this condition is not necessary. If G is undirected, or equivalently, if v → w implies w → v, then one can show that this condition is both necessary and sufficient. However, the directed case is more subtle.

Motivation: One can define a topological Markov chain as the space of all infinite paths through the graph G together with a shift that maps v0v1v2... to v1v2v3.... The value h defined above is the Gurevich entropy of this dynamical system, and it is of interest to know when the Gurevich entropy is finite.

This is sort of an anti-answer/extended comment. First let me comment that this is the same as the problem of determining which graphs have finite spectral radius. If your graph has adjacency matrix $A=(a_{ij})$, then the number of paths of length $n$, $v_i \to v_j$ is given by $(A^n)_{ij}$, and the spectral radius is given by $\limsup _{n\to \infty} (A^n) _{i,j}^{1/n}$. This value doesn't depend on the values of $i,j$ obviously, since we are in the connected (resp. strongly connected) case.
• You can avoid (or minimize) the problem dealing with loops, by making an additional assumption (to strong connectedness). Let $P$ be the transition matrix, and assume that there exist positive integers $K$ and $m$ such that $P^m \leq KP^{m+1}$ (entrywise) [this also works for directed graphs with weights, and more generally relatives of Markov chains]. Then you can say a lot (at the risk of self-advertising, see Eigenvectors and ratio limit theorems for Markov chains and their relatives, Journal d’Analyse Mathématique, 1999, Volume 78, Issue 1, pp 61–116), including limit ratio results, ... – David Handelman May 4 '17 at 17:14