9b. Graph symmetries

[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.

Moving now towards graph theory, that we are interested in, and which will in fact confirm and fine-tune the above conclusions, we have the following construction:

Theorem

Given a finite graph [math]X[/math], with vertices denoted [math]1,\ldots,N[/math], the symmetries of [math]X[/math], which are the permutations [math]\sigma\in S_N[/math] leaving invariant the edges,

[[math]] i-j\implies\sigma(i)-\sigma(j) [[/math]]

form a subgroup of the symmetric group, as follows, called symmetry group of [math]X[/math]:

[[math]] G(X)\subset S_N [[/math]]

As basic examples, for the empty graph, or for the simplex, we have [math]G(X)=S_N[/math].

Show Proof

Here the first assertion, regarding the group property of [math]G(X)[/math], is clear from definitions, because the symmetries of [math]X[/math] are stable under composition. The second assertion, regarding the empty graph and the simplex, is clear as well. So done, everything being trivial, and we have called this Theorem instead of Proposition because the construction [math]X\to G(X)[/math] will keep us busy, for the remainder of this book.

■

Let us work out now some more examples. As a first result, dealing with the simplest graph ever, passed the empty graphs and the simplices, we have:

Proposition

The symmetry group of the regular [math]N[/math]-gon

[[math]] \xymatrix@R=12pt@C=12pt{ &\bullet\ar@{-}[r]\ar@{-}[dl]&\bullet\ar@{-}[dr]\\ \bullet\ar@{-}[d]&&&\bullet\ar@{-}[d]\\ \bullet\ar@{-}[dr]&&&\bullet\ar@{-}[dl]\\ &\bullet\ar@{-}[r]&\bullet} [[/math]]

is the dihedral group [math]D_N=\mathbb Z_N\rtimes\mathbb Z_2[/math].

Show Proof

This is something that we know well from chapter 4, and with the remark, which is something new, that the notation [math]D_N[/math] for the group that we get, which is the correct one, is justified by the general group theory discussion before, with [math]N[/math] standing for the natural “dimensionality” of this group. To be more precise, geometrically speaking, the regular [math]N[/math]-gon is best viewed in [math]\mathbb R^N[/math], with vertices [math]1,\ldots,N[/math] at the standard basis:

[[math]] 1=(1,0,0,\ldots,0,0) [[/math]]

[[math]] 2=(0,1,0,\ldots,0,0) [[/math]]

[[math]] \ \ \ \vdots [[/math]]

[[math]] N=(0,0,0,\ldots,0,1) [[/math]]

But, with this interpretation in mind, we are led to an embedding as follows:

[[math]] D_N\subset S_N\subset O_N [[/math]]

We conclude from this that [math]N[/math] is the correct dimensionality of our group, and so is the correct label to be attached to the dihedral symbol [math]D[/math]. Of course, you might find this overly philosophical, or even a bit futile, but listen to this, there are two types of mathematicians in this world, those who use [math]D_N[/math] and those who use [math]D_{2N}[/math], and do not ask me why, but it is better to be in the first category, mathematicians using [math]D_N[/math].

■

Moving ahead, the problem is now, is Proposition 9.19 good news, or bad news? I don't know about you, but personally I feel quite frustrated by the fact that the computation there leads to [math]D_N=\mathbb Z_N\rtimes\mathbb Z_2[/math], instead to [math]\mathbb Z_N[/math] itself. I mean, how can a theory be serious, if there is no room there, or even an Emperor's throne, for the cyclic group [math]\mathbb Z_N[/math].

So, let us fix this. It is obvious that the construction in Theorem 9.18 will work perfectly well for the oriented graphs, or for the colored graphs, so let us formulate:

Definition

Given a generalized graph [math]X[/math], with vertices denoted [math]1,\ldots,N[/math], the symmetries of [math]X[/math], which are the permutations [math]\sigma\in S_N[/math] leaving invariant the edges,

[[math]] i-j\implies\sigma(i)-\sigma(j) [[/math]]

with their orientations and colors, form a subgroup of the symmetric group

[[math]] G(X)\subset S_N [[/math]]

called symmetry group of [math]X[/math].

Here, as before with the construction in Theorem 9.18, the fact that we obtain indeed a group is clear from definitions. Now with this convention in hand, we have:

Proposition

The symmetry group of the oriented [math]N[/math]-gon

[[math]] \xymatrix@R=16pt@C=16pt{ &\bullet\ar[r]&\bullet\ar[dr]\\ \bullet\ar[ur]&&&\bullet\ar[d]\\ \bullet\ar[u]&&&\bullet\ar[dl]\\ &\bullet\ar[ul]&\bullet\ar[l]} [[/math]]

is the cyclic group [math]\mathbb Z_N[/math].

Show Proof

This is clear from definitions, because once we choose a vertex [math]i[/math] and denote its image by [math]\sigma(i)=i+k[/math], the permutation [math]\sigma\in S_N[/math] leaving invariant the edges, with their orientation, must map [math]\sigma(i+1)=i+k+1[/math], [math]\sigma(i+2)=i+k+2[/math] and so on, and so must be an element of the cyclic group, in remainder modulo [math]N[/math] notation [math]\sigma=k\in\mathbb Z_N[/math].

■

With this done, and the authority of [math]\mathbb Z_N[/math] restored, let us work out some general properties of the construction [math]X\to G(X)[/math]. For simplicity we will restrict the attention to the usual graphs, as in Theorem 9.18, but pretty much everything will extend to the case of oriented or colored graphs. In fact, our policy in what follows will be that of saying nothing when things extend, and making a comment, when things do not extend.

As a first general result, coming as a useful complement to Theorem 9.18, we have:

Theorem

Having a group action on a graph [math]G\curvearrowright X[/math] is the same as saying that the action of [math]G[/math] leaves invariant the adjacency matrix [math]d[/math], in the sense that:

[[math]] d_{ij}=d_{g(i)g(j)}\quad,\quad\forall g\in G [[/math]]

Equivalently, the action must preserve the spectral projections of [math]d[/math]:

[[math]] d=\sum_\lambda\lambda P_\lambda\implies (P_\lambda)_{ij}=(P_\lambda)_{g(i)g(j)} [[/math]]

Thus, the symmetry group [math]G(X)\subset S_N[/math] is the subgroup preserving the eigenspaces of [math]d[/math].

Show Proof

As before with Theorem 9.18, a lot of talking in the statement, with everything being trivial, coming from definitions, and with the statement itself being called Theorem instead of Proposition just due to its theoretical importance.

■

Observe that Theorem 9.22 naturally leads us into colored graphs, because while the adjacency matrix is symmetric and binary, [math]d\in M_N(0,1)^{symm}[/math], the spectral projections [math]P_\lambda[/math] are also symmetric, but no longer binary, [math]P_\lambda\in M_N(\mathbb R)^{symm}[/math]. Moreover, these spectral projections [math]P_\lambda[/math] can have 0 on the diagonal, pushing us into allowing self-edges in our colored graph formalism. We are led in this way to the following statement:

Theorem

Having a group action on a colored graph [math]G\curvearrowright X[/math] is the same as saying that the action of [math]G[/math] leaves invariant the adjacency matrix [math]d[/math]:

[[math]] d_{ij}=d_{g(i)g(j)}\quad,\quad\forall g\in G [[/math]]

Equivalently, the action must preserve the spectral projections of [math]d[/math], as follows:

[[math]] d=\sum_\lambda\lambda P_\lambda\implies (P_\lambda)_{ij}=(P_\lambda)_{g(i)g(j)} [[/math]]

Moreover, when allowing self-edges, each [math]P_\lambda[/math] will correspond to a colored graph [math]X_\lambda[/math].

Show Proof

This follows indeed from the above discussion, and with some extra discussion regarding the precise colors that we use, as follows:

(1) When using real colors, the result follows from the linear algebra result regarding the diagonalization of real symmetric matrices, which tells us that the spectral projections of any such matrix [math]d\in M_N(\mathbb R)^{symm}[/math] are also real and symmetric, [math]P_\lambda\in M_N(\mathbb R)^{symm}[/math].

(2) When using complex colors, the result follows from the linear algebra result regarding the diagonalization of complex self-adjoint matrices, which tells us that the spectral projections of any such matrix [math]d\in M_N(\mathbb C)^{sa}[/math] are also self-adjoint, [math]P_\lambda\in M_N(\mathbb C)^{sa}[/math].

■

The point with the perspective brought by the above results is that, when using permutation group tools for the study of the groups [math]G\subset S_N[/math] acting on our graph, [math]G\curvearrowright X[/math], what will eventually happen is that these tools, once sufficiently advanced, will become very close to the regular tools for the study of [math]d[/math], namely the same sort of mixture of linear algebra, calculus and probability, so in the end we will have a unified theory.

But probably too much talking, just trust me, we won't be doing groups and algebra here just because we are scared by analysis, and by the true graph problems. Quite the opposite. And we will see illustrations for this harmony and unity later on.

Leaving now the oriented or colored graphs aside, as per our general graph policy explained above, as a second general result about [math]X\to G(X)[/math], we have:

Theorem

The construction [math]X\to G(X)[/math] has the property

[[math]] G(X)=G(X^c) [[/math]]

where [math]X\to X^c[/math] is the complementation operation.

Show Proof

This is clear from the construction of [math]G(X)[/math] from Theorem 9.18, and follows as well from the interpretation in Theorem 9.22, because the adjacency matrices of [math]X[/math], [math]X^c[/math] are related by the following formula, where [math]\mathbb I_N[/math] is the all-one matrix:

[[math]] d_X+d_{X^c}=\mathbb I_N-1_N [[/math]]

Indeed, since on the right we have the adjacency matrix of the simplex, which commutes with everything, commutation with [math]d_X[/math] is equivalent to commutation with [math]d_{X^c}[/math], and this gives the result, via the interpretation of [math]G(X)[/math] coming from Theorem 9.22.

■

In order to reach now to more advanced results, it is convenient to enlarge the attention to the colored graphs. Indeed, for the colored graphs, we can formulate:

Theorem

Having an action on a colored graph [math]G\curvearrowright X[/math] is the same as saying that the action leaves invariant the color components of [math]X[/math]. Equivalently, with

[[math]] d=\sum_{c\in C}cd_c [[/math]]

being the color decomposition of the adjacency matrix, with color components

[[math]] (d_c)_{ij}=\begin{cases} 1&{\rm if}\ d_{ij}=c\\ 0&{\rm otherwise} \end{cases} [[/math]]

the action must leave invariant all these color components [math]d_c[/math]. Thus, the symmetry group [math]G(X)\subset S_N[/math] is the subgroup which preserves all these matrices [math]d_c[/math].

Show Proof

As before with our other statements here, in the present section of this book, a lot of talking in the statement, with everything there being trivial.

■

I have this feeling that you might get to sleep, on the occasion of the present section, which is overly theoretical, this is how things are, we have to have some theory started, right. But, in the case it is so, I have something interesting for you, in relation with the above. Indeed, by combining Theorem 9.23 with Theorem 9.25, both trivialities, we are led to the following enigmatic statement, which all of the sudden wakes us up:

Theorem

Given an adjacency matrix of a graph [math]X[/math], which can be taken in a colored graph sense, [math]d\in M_N(\mathbb C)[/math], or even binary as usual,

[[math]] d\in M_N(0,1) [[/math]]

a group action [math]G\curvearrowright X[/math] must preserve all “spectral-color” components of this matrix, obtained by succesively applying the spectral decomposition, and color decomposition.

Show Proof

This is clear indeed by combining Theorem 9.23 and Theorem 9.25, and with the remark that, indeed, even for a usual binary matrix [math]d\in M_N(0,1)[/math] this leads to something non-trivial, because the spectral components of this matrix are no longer binary, and so all of the sudden, we are into colors and everything.

■

With the above result in hand, which is something quite unexpected, we are led into a quite interesting linear algebra question, which is surely new for you, namely: \begin{question} What are the spectral-color components of a matrix [math]d\in M_N(\mathbb C)[/math], or even of a usual binary matrix [math]d\in M_N(0,1)[/math]? \end{question} This question is something non-trivial, and we will be back to this on several occasions, and notably at the end of this book, when talking planar algebras in the sense of Jones , which provide the good framework for the study of such questions.

To be more precise, coming a bit in advance, we will see there that computing the spectral-color components of a matrix [math]d\in M_N(\mathbb C)[/math] is the same as computing the planar algebra generated by [math]d[/math], viewed as 2-box inside the tensor planar algebra.

General references

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