Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

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.

There is a not-so-recent survey on spectra of infinite graphs by B. Mohar and W. Woess (who also has a book on the related subject of random walks on infinite graphs and groups) but it doesn't go beyond the locally finite case and it doesn't treat directed graphs. They give many references there, including works of A. Torgasev, who studied spectral properties of graphs that aren't necessarily locally-finite.

Now spectra of infinite graphs can be approximated by the spectra of finite graphs which converge to our graph, and the reason why undirected graphs with finite spectral radius are easy to describe (locally finite and moreover bounded degree) is because one can check this property locally. That is I can look at the neighborhood of vertices with arbitrarily large degree and loops based on them to conclude that there is no upper bound on the spectral radius. However this property is completely lost in the case of directed graphs, given an outgoing edge or an incoming edge, I have no way of telling if they are part of a loop of some bounded length. So a characterization in terms of the degrees seems out of question. A geometric criterion is an other possibility, but as suggested from the related problem of determining transitivity/recurrence of graphs, maybe it is only possible if we are dealing with a Cayley graph.

So, I guess what I'm trying to say that a universal characterization of when an infinite digraph has finite spectral radius seems very hard, however one can deal with the cases which can be approximated through finite digraphs which have well understood spectral properties (for example, when you have a sparsity condition). I may be wrong, but it seems that spectral theory of directed graphs is a subject that hasn't been studied a lot, at least compared to the undirected case.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.