11c. Transitive actions

[math] \newcommand{\mathds}{\mathbb}[/math]

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.

With the above understood, let us get back to graphs. As already mentioned in the beginning of the previous section, the general principle is that representation theory and the Peter-Weyl theorems can help in understanding the group actions on graphs, [math]G\curvearrowright X[/math], by regarding these actions as unitary representations of [math]G[/math], as follows:

[[math]] u:G\to S_N\subset U_N [[/math]]

To be more precise, from a finite group and representation theory perspective, the whole graph symmetry problematics can be reformulated as follows: \begin{problem} Given a finite group representation [math]u:G\to U_N[/math]:

• Is this representation magic, in the sense that it factorizes through [math]S_N[/math]?
• If so, what are the [math]0-1[/math] graph adjacency matrices [math]d\in End(u)[/math]?
• Among these latter matrices, which ones generate [math]End(u)[/math]?

\end{problem} Generally speaking, these questions are quite difficult, ultimately leading into planar algebras in the sense of Jones , and despite having learned in this chapter some serious [math]C^*[/math]-algebra theory, and Peter-Weyl theory, we are not ready yet for such things. All this will have to wait for the end of this book, when we will discuss planar algebras.

In the meantime we can, however, discuss some elementary applications of Peter-Weyl theory to the study of graphs. As starting point, we have the following result:

Theorem

Given a transitive action [math]G\curvearrowright X[/math], any group character

[[math]] \chi:G\to\mathbb T [[/math]]

canonically produces an eigenfunction and eigenvalue of [math]X[/math], given by

[[math]] f(g(0))=\chi(g)\quad,\quad\lambda=\sum_{g(0)-0}\chi(g) [[/math]]

with [math]0\in X[/math] being a chosen vertex of the graph.

Show Proof

This is something elementary, coming from definitions, as follows:

(1) Let us fix a vertex [math]0\in X[/math], and consider the following set:

[[math]] S=\left\{g\in G\Big|g(0)-0\right\} [[/math]]

Observe that this set [math]S\subset G[/math] satisfies [math]1\notin S[/math], and also [math]S=S^{-1}[/math], due to:

[[math]] \begin{eqnarray*} g(0)-0 &\implies&g^{-1}(g(0))-g^{-1}(0)\\ &\implies&0-g^{-1}(0)\\ &\implies&g^{-1}(0)-0 \end{eqnarray*} [[/math]]

(2) As a comment here, the condition [math]1\notin S=S^{-1}[/math] is something quite familiar, namely the Cayley graph assumption from chapter 4. More about this in chapter 12 below, where we will systematically discuss the Cayley graphs, as a continuation of that material.

(3) Now given a character [math]\chi:G\to\mathbb T[/math] as in the statement, we can construct a function on the vertex set of our graph, [math]f:X\to\mathbb T[/math], according to the following formula:

[[math]] f(g(0))=\chi(g) [[/math]]

Observe that this function is indeed well-defined, everywhere on the graph, thanks to our assumption that the group action [math]G\curvearrowright X[/math] is transitive.

(4) Our claim now is that this function [math]f:X\to\mathbb T[/math] is an eigenfunction of the adjacency matrix of the graph. Indeed, we have the following computation, for any [math]g\in G[/math]:

[[math]] \begin{eqnarray*} (df)(g(0)) &=&\sum_{g(0)-j}f(j)\\ &=&\sum_{g(0)-h(0)}f(h(0))\\ &=&\sum_{g(0)-h(0)}\chi(h)\\ &=&\sum_{s\in S}\chi(sg)\\ &=&\sum_{s\in S}\chi(s)\chi(g)\\ &=&\sum_{s\in S}\chi(s)f(g(0)) \end{eqnarray*} [[/math]]

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

■

The above result is quite interesting, and as a continuation of the story, we have:

Theorem

In the context of the eigenfunctions and eigenvalues constructed above, coming from transitive actions [math]G\curvearrowright X[/math] and characters [math]\chi:G\to\mathbb T[/math]:

• For the trivial character, [math]\chi=1[/math], we obtain the trivial eigenfunction, [math]f=1[/math].
• When [math]G[/math] is assumed to be abelian, this gives the diagonalization of [math]d[/math].

Moreover, it is possible to generalize this construction, by using arbitrary irreducible representations instead of characters, and this gives again the diagonalization of [math]d[/math].

Show Proof

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

(1) This is clear from the construction from the proof of Theorem 11.27, which for trivial character, [math]\chi=1[/math], gives [math]f=1[/math], and [math]\lambda=|S|[/math], with the notations there.

(2) For an abelian group [math]G[/math], the characters form the dual group [math]\widehat{G}\simeq G[/math], and so we get a collection of [math]|\widehat{G}|=|G|=|X|[/math] eigenfunctions, as needed for diagonalizing [math]d[/math].

(3) In what regards the last assertion, the construction there is straightforward, with the final conclusion coming from the following formula, coming itself from Peter-Weyl:

[[math]] \sum_{r\in Irr(G)}(\dim r)^2=|G| [[/math]]

We will leave clarifying the details here as an instructive exercise, and we will come back to this in chapter 12, when discussing more systematically the Cayley graphs.

■

General references

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