12d. Infinite graphs
We would like to end this chapter, and this Part III of the present book, with a discussion regarding the infinite graphs. Generally speaking, the subject is heavily analytic, and it is beyond our purposes here to really get into this, at least at this stage of things. However, we have already seen some interesting examples of infinite graphs in the above, and also some of our basic definitions in the above extend in a quite straightforward way to the infinite graph setting, and all this is certainly worth an informal discussion.
To start with, an infinite graph [math]X[/math] is the same thing as a finite graph, except for the fact that the set of vertices is infinite, [math]|X|=\infty[/math], assumed countable. As in the finite group case, many interesting examples appear as Cayley graphs, as follows:
Associated to any discrete group [math]G= \lt S \gt [/math], with the generating set [math]S[/math] assumed to satisfy [math]1\notin S=S^{-1}[/math], is its Cayley graph, constructed as follows:
- The vertices are the group elements [math]g\in G[/math].
- Edges [math]g-h[/math] are drawn when [math]h=gs[/math], with [math]s\in S[/math].
Of course, we can talk as well about oriented Cayley graphs, and about colorings too, exactly as in the finite group case, but this discussion being quite informal anyway, we will focus on the most standard types of Cayley graphs, which are those above.
At the level of basic examples, we have two of them, as follows:
(1) Consider the group [math]\mathbb Z^N[/math], that is, the free abelian group on [math]N[/math] generators. We can represent the group elements as vectors in [math]\mathbb R^N[/math], in the obvious way, by using the embedding [math]\mathbb Z^N\subset\mathbb R^N[/math], and if we endow our group with its standard generating set, namely [math]S=\{\pm1_1,\ldots,\pm1_N\}[/math], written additively, the edges will appear precisely at the edges of the lattice [math]\mathbb Z^N\subset\mathbb R^N[/math]. Thus, the Cayley graph that we get is precisely this lattice:
(2) Consider now the free group [math]F_N=\mathbb Z^{*N}[/math] on [math]N[/math] generators, with its standard generating set, formed by the [math]N[/math] generators and their inverses, [math]S=\{g_1^{\pm1},\ldots,g_N^{\pm1}\}[/math]. As explained in chapter 6, when discussing trees, at [math]N=2[/math] the corresponding Cayley graph is as follows, and in general the picture is similar, with valence 4 being replaced by valence [math]4N[/math]:
So, these will be our basic examples of infinite graphs. And with the comment that these are both excellent graphs, not only aesthetically, but mathematically too.
Regarding now the general theory for the infinite graphs [math]X[/math], we can certainly talk about the corresponding symmetry groups [math]G(X)\subset S_\infty[/math], and other algebraic aspects, but the main questions remain those of analytic nature, notably in relation with:
\begin{question}
Given an infinite rooted graph [math]X[/math]:
- What is the number [math]L_k[/math] of length [math]k[/math] loops based at the root?
- What about the probability measure [math]\mu[/math] having the numbers [math]L_k[/math] as moments?
\end{question} We refer to chapter 1 for the computation for [math]\mathbb Z[/math], that is, for the Cayley graph of [math]\mathbb Z=F_1[/math], and to chapter 3 for some further computations, for the graphs [math]\mathbb N[/math] and [math]D_\infty[/math]. There are many interesting questions here, notably with the computation for the Cayley graphs of [math]\mathbb Z^N[/math] and [math]F_N[/math] at arbitrary [math]N\in\mathbb N[/math], leading to a lot of interesting mathematics, and for more on all this, we refer to any advanced probability book.
Finally, another set of interesting questions appears in relation with the Laplace operator introduced in chapter 5. Indeed, as explained there, for the Cayley graph of [math]\mathbb Z^N[/math], all this is related to the discretization of the basic equations of physics, via the finite element method. For more on all this, we refer to any good PDE book.
As a last topic of discussion, let us get back to the [math]N\to\infty[/math] considerations from the end of chapter 11. It is pretty much clear, from the discussion there, that, although this might seem related to the infinite graphs, the world of infinite graphs is in fact too narrow, for discussing such things. However, as good news, we have something new to say on that subject, by using the Brauer theorems from the previous section, namely:
Given a family of easy groups [math]G=(G_N)[/math], coming from a category of crossing partitions [math]D\subset P[/math], we have the following formula, with [math]D_k=D(0,k)[/math]:
More generally, we have the following formula, with [math]|.|[/math] being the number of blocks:
In the case of the groups [math]S=(S_N)[/math], [math]H=(H_N)[/math], and more generally [math]H^s=(H_N^s)[/math], we recover in this way, more conceptually, our previous probabilistic results.
There are several things going on here, the idea being as follows:
(1) To start with, we have the following formula, coming from Peter-Weyl, and then from easiness, with [math]u[/math] standing as usual for the fundamental representation:
(2) The point now is that, with [math]N\to\infty[/math], the above vectors [math]T_\pi[/math] become linearly independent. This is something not exactly trivial, the standard argument here being that it is enough to check this for the biggest possible category, [math]D=P[/math], and that for this category, the determinant of the Gram matrix of the vectors [math]T_\pi[/math] can be explicitly computed, thanks to a result of Lindstöm, and follows to be nonzero, with [math]N\to\infty[/math].
(3) Long story short, we have the first formula in the statement, at [math]t=1[/math]. As for the general [math]t \gt 0[/math] formula, this can be deduced as well, via more technical integration, called Weingarten formula, again by using Peter-Weyl and easiness.
(4) Finally, in what regards the examples as the end, for [math]S=(S_N)[/math], where [math]D=P[/math], and at [math]t=1[/math], it is notorious that the measure having as moments the Bell numbers [math]B_k=|P_k|[/math] is the Poisson law [math]p_1[/math]. Thus we have the general [math]H_N^s[/math] result at [math]s=1,t=1[/math], and the extension to the case of arbitrary parameters [math]s\in\mathbb N[/math] and [math]t \gt 0[/math] is straightforward.
And good news, that is all. In the hope that you liked this Part III of the present book, and of course with some apologies for going a bit off-topic on a number of occassions, as for instance with this Theorem 12.35 that we just proved, featuring no graphs. The point, however, with all this, is that all this learning will be very useful, for what comes next.
General references
Banica, Teo (2024). "Graphs and their symmetries". arXiv:2406.03664 [math.CO].