1c. Walks on graphs

This article was automatically generated from a tex file and may contain conversion errors. If permitted, you may login and edit this article to improve the conversion.

Have you ever played chess, or simply observed a cat in action. There are all sorts of paths and combinations that can be followed, and the problem is that of quickly examining all these possibilities, with the series of conclusions being typically something on type damn, damn, damn, damn, damn, yes. With the yes followed by some action.

Mathematically speaking, this brings us into walks on graphs. And here, as usual, we get into the adjacency matrix [math]d[/math], thanks to the following key result:

Theorem

Given a graph [math]X[/math], with adjacency matrix [math]d\in M_N(0,1)[/math], we have:

[[math]] (d^k)_{ij}=\#\Big\{i=i_0-i_1-\ldots-i_{k-1}-i_k=j\Big\} [[/math]]

That is, the [math]k[/math]-th power of [math]d[/math] describes the length [math]k[/math] paths on [math]X[/math].

Show Proof

According to the usual rule of matrix multiplication, the formula for the powers of the adjacency matrix [math]d\in M_N(0,1)[/math] is as follows:

[[math]] \begin{eqnarray*} (d^k)_{i_0i_k} &=&\sum_{i_1,\ldots,i_{k-1}}d_{i_0i_1}d_{i_1i_2}\ldots d_{i_{k-1}i_k}\\ &=&\sum_{i_1,\ldots,i_{k-1}}\delta_{i_0-i_1}\delta_{i_1-i_2}\ldots\delta_{i_{k-1}-i_k}\\ &=&\sum_{i_1,\ldots,i_{k-1}}\delta_{i_0-i_1-\ldots-i_{k-1}-i_k}\\ &=&\#\Big\{i_0-i_1-\ldots-i_{k-1}-i_k\Big\} \end{eqnarray*} [[/math]]

Thus, we are led to the conclusion in the statement.

■

Of particular interest are the paths which begin and end at the same point. These are called loops, and in the case of loops, Theorem 1.14 particularizes as follows:

Theorem

Given a graph [math]X[/math], with adjacency matrix [math]d\in M_N(0,1)[/math], we have:

[[math]] (d^k)_{ii}=\#\Big\{k-{\rm loops\ based\ at\ }i\in I\Big\} [[/math]]

Also, the total number of [math]k[/math]-loops on [math]X[/math], at various vertices, is the number

[[math]] Tr(d^k)=\sum_i(d^k)_{ii} [[/math]]

which can be computed by diagonalizing [math]d[/math].

Show Proof

There are several things going on here, the idea being as follows:

(1) The first assertion follows from Theorem 1.14, which at [math]i=j[/math] gives the following formula, which translates into the first formula in the statement:

[[math]] (d^k)_{ii}=\#\Big\{i=i_0-i_1-\ldots-i_{k-1}-i_k=i\Big\} [[/math]]

(2) Regarding now the second assertion, this follows from the first one, simply by summing over all the vertices [math]i\in X[/math], which gives, as desired:

[[math]] Tr(d^k)=\sum_i\#\Big\{k-{\rm loops\ based\ at\ }i\in I\Big\} [[/math]]

(3) Finally, the third assertion is something well-known from linear algebra, the idea being that once we diagonalize a matrix, [math]A=PDP^{-1}[/math], we have:

[[math]] \begin{eqnarray*} A=PDP^{-1} &\implies&A^k=PD^kP^{-1}\\ &\implies&Tr(A^k)=Tr(D^k) \end{eqnarray*} [[/math]]

Thus, back now to our graph case, if we denote by [math]\lambda_1,\ldots,\lambda_N\in\mathbb R[/math] the eigenvalues of [math]d[/math], then the formula of the trace of [math]d^k[/math], that we are interested in, is as follows:

[[math]] Tr(d^k)=\lambda_1^k+\ldots+\lambda_N^k [[/math]]

Here we have used the fact that [math]d[/math], which is a real symmetric matrix, is indeed diagonalizable, and with real eigenvalues. You might perhaps know this from linear algebra, and if not do not worry, we will discuss all this in detail in chapter 2.

■

All the above is quite interesting, and adds to our investigations from the previous section, suggesting as well to get into the diagonalization question for the adjacency matrix [math]d\in M_N(0,1)[/math]. We will do this as soon as possible, and more precisely starting from chapter 2 below. But before that, we still have to discuss some examples for all this, plus a number of other topics of general interest, not needing diagonalization.

Let us start with the examples. Unfortunately, here everything is quite complicated, because even for very simple graphs [math]X[/math], go count the loops directly, via recurrences and so on, that is a lot of combinatorics, which is invariably non-trivial. Or go compute the powers [math]d^k[/math] without diagonalizing [math]d[/math], that is a lot of heavy work too.

So, as a first philosophical question, what are the simplest graphs [math]X[/math], that we can try to do some loop computations for? And here, we have 3 possible answers, as follows:

\begin{fact} The following are graphs [math]X[/math], with a distinguished vertex [math]0\in X[/math]:

The circle graph, having [math]N[/math] vertices, with [math]0[/math] being one of the vertices.
The segment graph, having [math]N[/math] vertices, with [math]0[/math] being the vertex at left.
The segment graph, having [math]2N+1[/math] vertices, with [math]0[/math] being in the middle.

\end{fact} So, let us start with these. For the circle, the computations are quite non-trivial, and you can try doing some, in order to understand what I am talking about. The problem comes from the fact that loops of length [math]k=0,2,4,6,\ldots[/math] are quite easy to count, but then, once we pass [math]k=N[/math], the loops can turn around the circle or not, and they can even turn several times, and so on, and all this makes the count too complicated. In addition, again due to loop turning, when [math]N[/math] is odd, we have as well loops of odd length.

As for the two segment graphs, here the computations look again complicated, and even more complicated than for the circle, because, again, once we pass [math]k=N[/math] many things can happen, and this makes the count too complicated. And here, again you can try doing some computations, in order to understand what I am talking about.

So, shall we give up, in waiting for more advanced techniques, say coming from diagonalization? This would be a wise decision, but before that, let us pull an analysis trick, and formulate the following result, which is of course something informal, and modest:

Theorem

For the circle graph, having [math]N[/math] vertices, the number of length [math]k[/math] loops based at one of the vertices is approximately

[[math]] L_k\simeq\frac{2^k}{N} [[/math]]

in the [math]k\to\infty[/math] limit, when [math]N[/math] is odd, and is approximately

[[math]] L_k\simeq\begin{cases} \frac{2^{k+1}}{N}&(k\ {\rm even})\\ 0&(k\ {\rm odd}) \end{cases} [[/math]]

also with [math]k\to\infty[/math], when [math]N[/math] is even. However, in what regards the two segment graphs, we can expect here things to be more complicated.

Show Proof

This is something not exactly trivial, and with the way the statement is written, which is clearly informal, witnessing for that. The idea is as follows:

(1) Consider the circle graph [math]X[/math], with vertices denoted [math]0,1,\ldots,N-1[/math]. Since each vertex has valence 2, any length [math]k[/math] path based at 0 will consist of a binary choice at the beginning, then another binary choice afterwards, and so on up to a [math]k[/math]-th binary choice at the end. Thus, there is a total of [math]2^k[/math] such paths, based at 0, and having length [math]k[/math].

(2) But now, based on the obvious “uniformity” of the circle, we can argue that, in the [math]k\to\infty[/math] limit, the endpoint of such a path will become random among the vertices [math]0,1,\ldots,N-1[/math]. Thus, if we want this endpoint to be 0, as to have a loop, we have [math]1/N[/math] chances for this to happen, so the total number of loops is [math]L_k\simeq 2^k/N[/math], as stated.

(3) With the remark, however, that the above argument works fine only when [math]N[/math] is odd. Indeed, when [math]N[/math] is even, the endpoint of a length [math]k[/math] path will be random among [math]0,2,\ldots,2N-2[/math] when [math]k[/math] is even, and random among [math]1,3,\ldots,2N-1[/math] when [math]k[/math] is odd. Thus for getting a loop we must assume that [math]k[/math] is even, and in this case the number of such loops is the total number of length [math]k[/math] paths, namely [math]2^k[/math], approximately divided by [math]N/2[/math], the number of points in [math]\{0,2,\ldots,2N-2\}[/math], which gives [math]L_k=2^k/(N/2)[/math], as stated.

(4) All this was of course a bit borderline, I know, with respect to what rigorous mathematics is supposed to be, but honestly, I think that the argument is there, and good, in short I trust this proof. Needless to say, we will be back to all this later, with some better tools for attacking such problems, and with full rigor, at that time.

(5) Moving ahead now to the segment graphs, it is pretty much clear that for both, we lack the “uniformity” needed in (2), and this due to the 2 endpoints of the segment. In fact, thinking well, these graphs are no longer 2-valent, again due to the 2 endpoints, each having valence 1, and so even (1) must be fixed. And so, we will stop here.

■

All this is obviously not very good news, and so again, as question, shall we give up, in waiting for more advanced techniques, say coming from diagonalization?

Well, instead of giving up, let us look face-to-face at the difficulties that we met. We are led this way, after analyzing the situation, to the following thought: \begin{thought} The difficulties that we met, with the circle and the two segments, come from the fact that our loops are not “free to move”,

for the circle, because these can circle around the circle,
for the segments, obviously because of the endpoints,

and so our difficulties will dissapear, and we will be able to do our exact loop count, once we find a graph [math]X[/math] where the loops are truly “free to move”. \end{thought} Thinking some more, all this definitely buries the first interval graph, where the vertex [math]0[/math] is one of the endpoints. However, we can still try to recycle the circle, by unwrapping it, or extend our second interval graph up to [math]\infty[/math]. But in both cases what we get is the graph [math]\mathbb Z[/math] formed by the integers. So, let us formulate the following definition:

Definition

An infinite graph is the same thing as a finite graph, but now with an infinity of vertices, [math]|X|=\infty[/math]. As a basic example, we have [math]\mathbb Z[/math]. We also have [math]\mathbb N[/math].

Leaving aside now [math]\mathbb N[/math], which looks more complicated, let us try to count the length [math]k[/math] paths on [math]\mathbb Z[/math], based at [math]0[/math]. At [math]k=1[/math] we have [math]2[/math] such paths, ending at [math]-1[/math] and [math]1[/math], and the count results can be pictured as follows, with everything being self-explanatory:

[[math]] \xymatrix@R=5pt@C=15pt{ \circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\bullet\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\\ &&1&&1 } [[/math]]

At [math]k=2[/math] now, we have 4 paths, one of which ends at [math]-2[/math], two of which end at 0, and one of which ends at 2. The results can be pictured as follows:

[[math]] \xymatrix@R=5pt@C=15pt{ \circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\bullet\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\\ &1&&2&&1 } [[/math]]

At [math]k=3[/math] now, we have 8 paths, the distribution of the endpoints being as follows:

[[math]] \xymatrix@R=5pt@C=15pt{ \circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\bullet\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\\ &1&&3&&3&&1 } [[/math]]

As for [math]k=4[/math], here we have 16 paths, the distribution of the endpoints being as follows:

[[math]] \xymatrix@R=5pt@C=15pt{ \circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\bullet\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\\ &1&&4&&6&&4&&1 } [[/math]]

And good news, we can see in the above the Pascal triangle. Thus, eventually, we found the simplest graph ever, namely [math]\mathbb Z[/math], and we have the following result about it:

Theorem

The paths on [math]\mathbb Z[/math] are counted by the binomial coefficients. In particular, the [math]2k[/math]-paths based at [math]0[/math] are counted by the central binomial coefficients,

[[math]] \binom{2k}{k}\simeq\frac{4^k}{\sqrt{\pi k}} [[/math]]

with the estimate, in the [math]k\to\infty[/math] limit, coming from the Stirling formula.

Show Proof

This basically follows from the above discussion, as follows:

(1) In what regards the count, we certainly have the Pascal triangle, as discovered above, and the rest is just a matter of finishing. There are many possible ways here, a straightforward one being that of arguing that the number [math]C_k^l[/math] of length [math]k[/math] loops [math]0\to l[/math] is subject, due to the binary choice at the end, to the following recurrence relation:

[[math]] C_k^l=C_{k-1}^{l-1}+C_{k-1}^{l+1} [[/math]]

But this is exactly the recurrence for the Pascal triangle, so done with the count.

(2) In what regards the estimate, this follows indeed from Stirling, as follows:

[[math]] \begin{eqnarray*} \binom{2k}{k} &=&\frac{(2k)!}{k!k!}\\ &\simeq&\left(\frac{2k}{e}\right)^{2k}\sqrt{4\pi k}\times\left(\frac{e}{k}\right)^{2k}\frac{1}{2\pi k}\\ &=&\frac{4^k}{\sqrt{\pi k}} \end{eqnarray*} [[/math]]

Thus, we are led to the conclusions in the statement.

■

Not bad all this. We will be back to other graphs, such as [math]\mathbb N[/math], which is still left, or the circle, or the two segments, and many more, later on. But before that, we still have to discuss a number of other topics of general interest, including coloring.

General references

Banica, Teo (2024). "Graphs and their symmetries". arXiv:2406.03664 [math.CO].