9
$\begingroup$

Observation: If we take the graph with two vertices, A and B, with a loop {A,A} and undirected edge {A,B}, then the number of closed walks $W_n$ of length $n \geq 1$ starting from A we get $W_1=1$ (counting AA), $W_2=2$ (counting AAA and ABA) and $W_n=W_{n-1}+W_{n-2}$, i.e. the Fibonacci numbers.

Question: Which types of recurrences can be realised as the number of closed walks from the origin of a graph?

More generally, which types of recurrences can be realised as the number of walks of some type in some graph?

If we can interpret a recurrence relation as the number of walks in a graph in some way, then might be able to use spectral theory to find formulas for the sequence. (see: Frank Harary and Allen J. Schwenk, The spectral approach to determining the number of walks in a graph. Pacific J. Math. Volume 80, Number 2 (1979), 443-449.)

$\endgroup$
4
  • $\begingroup$ Duplicate? mathoverflow.net/questions/3939/… $\endgroup$ Oct 29, 2010 at 8:04
  • $\begingroup$ Must the graphs be undirected? (Your example has undirected edges, but you don't state that in your question itself.) $\endgroup$ Oct 29, 2010 at 17:26
  • $\begingroup$ At this point, I don't care about the specifics, just as long as it's possible to count walks. $\endgroup$ Oct 29, 2010 at 21:40
  • $\begingroup$ @Mike-Spivey, the undirected graph can be transformed into a directed graph, retaining the "undirectedness" of the original graph by: $$ $$ replacing each undirected edge between two vertices with a pair of directed edges between the same two vertices. A directed graph version of this allows for a direct correspondence to the class of regular languages accepted by a Nondeterministic Finite Automaton. (see my comment below Qiaochu Yuan's answer on this page) $\endgroup$ Oct 30, 2010 at 8:02

2 Answers 2

2
$\begingroup$

Okay, so it's not quite a duplicate because I guess you're asking about initial conditions as well. The generating functions of the sequences $a_n$ which have this property are called $\mathbb{N}$-recognizable or $\mathbb{N}$-rational in the literature, and they are essentially (precisely?) the generating functions of word lengths in regular languages (star example: the look-and-say sequence). Not all rational functions with non-negative integer coefficients are $\mathbb{N}$-rational; see for example the counterexamples in these slides. These slides also seem relevant.

Stanley's Enumerative Combinatorics discusses some of these issues, in particular look at Section 4.7.

$\endgroup$
2
  • $\begingroup$ Let me mention that one class of examples includes all recurrences with non-negative integer coefficients and non-negative integer initial conditions; the proof is to take the graph whose adjacency matrix is the companion matrix of the characteristic polynomial. This idea can be used to give a combinatorial proof of the Newton-Girard identities: see qchu.wordpress.com/2009/08/23/… and qchu.wordpress.com/2009/11/04/… . $\endgroup$ Oct 29, 2010 at 11:54
  • 1
    $\begingroup$ @qiaochu-yuan, I believe that they are precisely / exactly the same as regular languages. A perfect correspondence exists between the regular languages and the Finite State Machine representation of these regular languages as directed graphs of a probabilistic automaton. In this case, every node is an accepting node, and replace every undirected edge with a pair of directed edges. Now, in Formal Language Theory, this graph is a representation of the FSM which accepts that regular language. $\endgroup$ Oct 30, 2010 at 5:27
1
$\begingroup$

If the motivation is to use spectral methods, then there is no need to interpret things as a graph. To count walks in a graph one gets a recurrence relation (given by the adjacency matrix) and proceeds using spectral methods. If $A$ is an $n \times n$ matrix and $x_0$ a column vector then setting $x_{m+1}=Ax_m$ leads to a system of $n$ first order linear recurrences in the $n$ positions. In most non-degenerate cases one can get a single $nth$ order recurrence for a particular entry (or linear combination of entries). Similarly for the $r,c$ entry of $A^m$, the trace and other linear combinations. Really one is studying the entries of $A^m$ since $A^mx_0=x_m$. In the case that one starts with an $nth$ order linear recurrence one just has a rather special kind of graph.

That said, if the entries of $A$ are non-negative integers then one can naturally interpret $A^m$ as counting length $m$ walks in a certain $n$-vertex directed graph with multiple edges and loops allowed. For an arbitrary $n \times n$ matrix with entries from a ring one could consider the entries as multiplicitive edge weights on the complete $n$-vertex directed graph (with loops) and $A^m$ as recording in position $u,v$ the total weight of the length $m$ paths starting at $u$ and ending at $v$.

But again, once one enjoys the fact that every linear recurrence can be interpreted as a weighted path enumeration problem, there is usual not much motivation to actually do so. I suppose that the initial conditions are not really accounted for in this sketch, but they don't really come into solving recurrence relations until the very end.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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