Graph products
10a. Small graphs
We have seen in the previous chapter how to associate to any finite graph [math]X[/math] its symmetry group [math]G(X)[/math], and we have seen as well some basic properties of the correspondence [math]X\to G(X)[/math]. Motivated by this, our goal in this chapter will be that of systematically computing the symmetry groups [math]G(X)[/math], for as many graphs [math]X[/math] that we can.
Easy task, you would say, because we already have [math]G(X)[/math] for all the [math]N[/math]-gons, and since [math]\infty+n=\infty[/math], no need for new computations, in order to improve our results. Jokes left aside, we certainly need here some precise objectives and strategy, so let us formulate:
\begin{goal}
Take the integers one by one, [math]N=2,3,4,5,6,\ldots[/math] and look at all graphs of order [math]|X|=N[/math]. For each such graph, find a decomposition of type
with [math]\times[/math] being a certain graph product, and [math]|Y|,|Z| \lt N[/math], then work out a formula of type
with [math]\times[/math] being a certain group product, adapted to the above graph product, as to solve the problem by recurrence. When stuck, find some ad-hoc methods for dealing with [math]X[/math]. \end{goal} This plan sounds quite reasonable, so let us see how this works. At very small values of [math]N=2,3,4,5,6,\ldots[/math] things are quite clear, and in fact no even need here for a plan, because the symmetry group is just obvious. However, since we will deal with higher [math]N[/math] afterwards, it is useful to resist the temptation of simply recording the value of [math]G(X)[/math], and stick to the above plan, or at least record the various graph products [math]\times[/math] that we meet on the way, and the corresponding adapted group products [math]\times[/math] too.
Getting started now, at [math]N=2,3[/math] everything is trivial, but let us record this:
At [math]N=2,3[/math] we have, with no product operations involved:
- Two points [math]\bullet\ \bullet[/math] and the segment [math]\bullet-\bullet[/math], with symmetry group [math]\mathbb Z_2[/math].
- Three points [math]\bullet\ \bullet\ \bullet[/math] and the triangle [math]\triangle[/math], with symmetry group [math]S_3[/math].
- The graphs [math]\bullet-\bullet\ \ \ \bullet[/math] and [math]\bullet-\bullet-\bullet[/math], with symmetry group [math]\mathbb Z_2[/math].
All this is self-explanatory, but us record however a few observations:
(1) All pairs of graphs in the above appear from each other via complementation, with this being obvious in all cases, save perhaps for (3), where the graphs are as follows:
(2) Now since we have [math]G(X)=G(X^c)[/math], this suggests listing our graphs up to complementation. However, this is a quite bad idea, in practice, because believe me, you will end up sleeping bad at night, with thoughts of type damn, I forgot in my list this or that beautiful graph, only to realize later, after some computations in your head, that the graph in question was in fact complementary to a less beautiful graph, from your list.
(3) Another comment, subjective too, concerns the labeling of the groups that we found. For instance [math]\mathbb Z_1=D_1=S_1[/math], and [math]\mathbb Z_2=D_2=S_2[/math], and [math]D_3=S_3[/math]. Our policy will be that of regarding [math]\mathbb Z_N[/math] as the simplest group, because this is what this group is, and using it preferentially. Followed by [math]S_N[/math], because at least in questions regarding permutation groups, this is the second simplest group. As for [math]D_N[/math] and other more specialized groups, we will only use them when needed, and with [math]D_N[/math] being third on our list.
(4) As a mathematical comment now, however trivial, the fact that we have no product operations involved conceptually comes from the fact that [math]2,3[/math] are both prime.
(5) However, in relation with this, observe that we have [math]S_3=D_3=\mathbb Z_3\rtimes\mathbb Z_2[/math], but this does not correspond to anything, at the level of the graphs [math]\bullet\ \bullet\ \bullet[/math] and [math]\triangle[/math]. So, good to know, the world of graphs is somehow more rigid than that of the groups.
At [math]N=4[/math] now, which is both big enough, and composite, several new phenomena appear. First, we have the presence of “ugly” graphs, of the following type, that no one will be ever interested in, and which do not decompose as products either:
So, leaving aside now this ugly graph, and its symmetry group [math]\mathbb Z_2[/math], and all sorts of other similar graphs, functioning on the same principle “too many vertices, for not much symmetry for the buck”, we are left, quite obviously, with the transitive graphs, which do have lots of symmetry. So, let us update our Goal 10.1, as follows:
\begin{update}
In relation with our original program, we will restrict the attention to the transitive graphs. Moreover, we will list these transitive graphs following a
scheme, according to their valence, and coupled via complementation. \end{update} Here the scheme mentioned at the end is what comes out from Proposition 10.2 (1,2,3), and this is something quite self-explanatory, that will become clear as we work out more examples. Going back now to [math]N=4[/math], with the above update made, we have:
The transitive graphs at [math]N=4[/math] are at follows:
- Valence [math]0,3[/math]: the empty graph and the tetrahedron, with symmetry group [math]S_4[/math],
[[math]] \xymatrix@R=40pt@C=40pt{ \bullet&\bullet&\bullet\ar@{-}[d]\ar@{-}[dr]&\bullet\ar@{-}[d]\ar@{-}[l]\ar@{-}[dl]\\ \bullet&\bullet&\bullet\ar@{-}[r]&\bullet } [[/math]]
- Valence [math]1,4[/math]: the two segments and the square, namely
[[math]] \xymatrix@R=40pt@C=40pt{ \bullet\ar@{-}[dr]&\bullet\ar@{-}[dl]&\bullet\ar@{-}[d]&\bullet\ar@{-}[d]\ar@{-}[l]\\ \bullet&\bullet&\bullet\ar@{-}[r]&\bullet } [[/math]]both products of a segment with itself, with symmetry group [math]D_4=\mathbb Z_4\rtimes\mathbb Z_2[/math].
As before with Proposition 10.2, all this is trivial and self-explanatory, but some comments are in order, in regards with the last assertions, namely:
(1) Regarding the “products of a segment with itself” assertion, this is of course something informal, and very intuitive, which remains of course to be clarified. Thus, to be added on our to-do list, two different product operations for graphs [math]\times[/math] to be constructed, as to make this work. And no worries for this, we will be back to it, very soon.
(2) As another comment, even when assuming that we managed to solve (1), with some suitable product operations for graphs [math]\times[/math] constructed, it is quite unclear how we can get, via these operations, the formula [math]G(X)=\mathbb Z_4\rtimes\mathbb Z_2[/math]. Thus, a potential source of worries, and again, this is just a comment, and we will be back to this, very soon.
At [math]N=5[/math] now, a small prime, things a bit similar to [math]N=2,3[/math], and we have:
The transitive graphs at [math]N=5[/math] are as follows:
- Valence [math]0,4[/math]: the empty graph and the simplex, with [math]G(X)=S_5[/math].
- Valence [math]1,3[/math]: none, since [math]N=5[/math] is odd.
- Valence [math]2[/math]: the pentagon, self-complementary, with [math]G(X)=D_5[/math].
As before, everything is self-explanatory, with however the fact that the pentagon is self-dual being remarkable, definitely to be remembered, the picture being:
Thus, we are led to the conclusions in the statement.
At [math]N=6[/math] now, composite number, things get interesting again, and we have:
The transitive graphs at [math]N=6[/math] are as follows:
- Valence [math]0,5[/math]: the empty graph and the simplex, with [math]G(X)=S_6[/math].
- Valence [math]1,4[/math]: the [math]3[/math] segments and the star graph, with [math]G(X)=H_3[/math].
- Valence [math]2,3[/math]: the hexagon and the prism, with [math]G(X)=D_6[/math].
- Valence [math]2,3[/math] too: the [math]2[/math] triangles and the wheel/utility graph, products.
As before, everything here is self-explanatory, the idea being as follows:
(1) Nothing special to be said about the empty graph and the simplex.
(2) At valence 1, we obviously have as only solution the 3 segments. Regarding now the complementary graph, this looks as follows, like a star:
As for the symmetry group assertion, this follows from what we know about the hyperoctahedral groups. Indeed, the hyperoctahedral group [math]H_3[/math] appears by definition as symmetry group of the centered hypercube [math]\square_3\subset\mathbb R^3[/math]. But this group is also, obviously, the symmetry group of the space formed by the segments [math][-1,1][/math] along each coordinate axis. We conclude that the symmetry group of the 3 segments is indeed [math]H_3[/math].
(3) At valence 2 now, which is the case left, along with the complementary case of valence 3, we have two solutions, namely the hexagon and the 2 triangles. Regarding the hexagon, have we have [math]G(X)=D_6[/math], and the only issue left is that of identifying the complementary graph. But this complementary graph is as follows, and when thinking a bit, by pulling one triangle, and then rotating it, you will see a prism here:
(4) Still at valence 2, and complementary valence 3, it remains to discuss the 2 triangles, and its complement. Nothing much to be said about the 2 triangles, but in what regards the complementary graph, there is something tricky here. Indeed, we can draw this complementary graph as follows, making it clear that we have a wheel:
But now, that we have this wheel, let us color the vertices as follows:
We can see here a bipartite graph, and by pulling apart the black and white vertices, we conclude that our graph is the utility graph, that we met in chapter 4:
Finally, in what regards the computation of the symmetry group, the best here is to go back to the original 2 triangles, and draw them as follows:
But this is obviously a product graph, namely a product between a segment and a triangle, so the symmetry group must appear as some sort of product of [math]\mathbb Z_2[/math] and [math]S_3[/math]. We will leave the details and computations here for a bit later, when discussing more in detail product operations, and the computation of the corresponding symmetry groups.
As an interesting conclusion coming from the above discussion, which is something useful and practice, that you always forget, let us record the following fact: \begin{conclusion} The utility graph is the wheel,
with this being best seen via the [math]2[/math] triangles missing, in each case. \end{conclusion} Here the first assertion looks a bit like a joke, because what can be more useful to mankind, than a wheel. However, it is not from here that the name “utility graph” comes from. The story here involves 3 companies, selling gas, water and electricity to 3 customers, and looking for a way to arrange their underground tubes and wires as not to cross. Thus, they are looking to implement their “utillity graph”, which is the above one, in a planar way, and as we know well from chapter 7, this is not possible, and even leads to some deep theorems about planar graphs, those of Kuratowski and Wagner.
Back to work now, and to our graph enumeration program, at [math]N=7[/math], which a small prime, things are a bit similar to those at [math]N=2,3,5[/math], as follows:
The transitive graphs at [math]N=7[/math] are as follows:
- Valence [math]0,6[/math]: the empty graph and the simplex, with [math]G(X)=S_7[/math].
- Valence [math]1,5[/math]: none, since [math]N=7[/math] is odd.
- Valence [math]2,4[/math]: the heptagon and its complement, with [math]G(X)=D_7[/math].
- Valence [math]3[/math]: none, since [math]N=7[/math] is odd.
As before, everything here is self-explanatory, coming from definitions, and from facts that we know well, with perhaps the only thing to be worked out being the picture of the complement of the heptagon, which looks as follows:
Thus, we are led to the conclusions in the statement.
10b. Medium graphs
Let us discuss now the graphs with bigger number of vertices, [math]N\geq8[/math]. In what regards the graphs with [math]8[/math] vertices, to start with, with [math]N=8[/math] being a multiply composite number, things get more complicated, with several new phenomena appearing, as follows:
The transitive graphs at [math]N=8[/math] are as follows:
- Valence [math]0,7[/math]: the empty graph and the simplex, with [math]G(X)=S_8[/math].
- Valence [math]1,6[/math]: the [math]4[/math] segments and the thick tyre, products.
- Valence [math]2,5[/math]: the octagon and the big globe, with [math]G(X)=D_8[/math].
- Valence [math]2,5[/math] too: the [math]2[/math] squares and the holy cross, products.
- Valence [math]3,4[/math]: the [math]2[/math] tetrahedra and the stop sign, products.
- Valence [math]3,4[/math] too: the cube and the metal cross, with [math]G(X)=H_3[/math].
- Valence [math]3,4[/math] too: the wheel and the big tent, with [math]G(X)=S_8[/math].
As before, everything here is self-explanatory, the idea being as follows:
(1) Nothing much to be said about the empty graph, and its complement.
(2) At valence [math]1,6[/math] we have the [math]4[/math] segments, obviously a product, whose symmetry group we will compute later, and its complement, the thick tyre, which is as follows:
(3) At valence [math]2,5[/math] we have the octagon, whose symmetry group is [math]G(X)=D_8[/math], and its complement the big globe, which looks crowded too, as follows:
(4) At valence [math]2,5[/math] too we have the [math]2[/math] squares, obviously a product, whose symmetry group we will compute later, and its complement the holy cross, as follows:
(5) At valence [math]3,4[/math] now, we first have the [math]2[/math] tetrahedra, obviously a product, whose symmetry group we will compute later, and its complement, the stop sign:
(6) Still at valence [math]3,4[/math], we have as well the cube, whose symmetry group is [math]G(X)=H_3[/math], as we know well, and its complement the metal cross, which is as follows:
(7) Finally, still at valence [math]3,4[/math], we have as well the wheel, whose symmetry group is [math]G(X)=S_8[/math], and its complement the big tent, which is as follows:
Thus, we are led to the conclusions in the statement.
At [math]N=9[/math] now, things get again easier, but still non-trivial, as follows:
The transitive graphs at [math]N=9[/math] are as follows:
- Valence [math]0,8[/math]: the empty graph and the simplex, with [math]G(X)=S_9[/math].
- Valence [math]2,6[/math]: the nonagon and its complement, with [math]G(X)=D_9[/math].
- Valence [math]2,6[/math] too: the [math]3[/math] triangles and its complement, products.
- Valence [math]4[/math]: the torus graph and its complement, products.
- Valence [math]4[/math] too: the wheel and its complement, with [math]G(X)=D_9[/math].
As before, everything here is self-explanatory, the comments being:
(1) Nothing much to be said about the empty graph, and its complement.
(2) Nothing much to be said either about the nonagon, and its complement.
(3) Regarding the 3 triangles, and its complement, we will compute here [math]G(X)[/math] later.
(4) At valence [math]4[/math] we have an interesting graph which appears, namely the discrete torus, which is the simplest discretization of a torus, as follows, and whose symmetry group we will compute later, when discussing in detail the product operations:
(5) Also at valence 4, we have the wheel and its complement, with the wheel being drawn as follows, forced by the fact that 9 is odd, with two spokes at each vertex:
Thus, we are led to the conclusions in the statement.
At [math]N=10[/math] now, things get really tough, and we have:
The transitive graphs at [math]N=10[/math] are as follows:
- Valence [math]0,9[/math]: the empty graph and the simplex, with [math]G(X)=S_{10}[/math].
- Valence [math]1,8[/math]: the [math]5[/math] segments and its complement, products.
- Valence [math]2,7[/math]: the decagon and its complement, with [math]G(X)=D_{10}[/math].
- Valence [math]2,7[/math] too: the [math]2[/math] pentagons and its complement, product.
- Valence [math]3,6[/math]: the wheel and its complement, with [math]G(X)=D_{10}[/math].
- Valence [math]3,6[/math] too: the pentagon prism and its complement, products.
- Valence [math]3,6[/math] too: the Petersen graph and its complement.
- Valence [math]4,5[/math]: the two [math]5[/math]-simplices, and its complement, products.
- Valence [math]4,5[/math] too: the [math]5[/math]-simplex prism and the torch, products.
- Valence [math]4,5[/math] too: the reinforced wheel and its complement, with [math]G(X)=D_{10}[/math].
- Valence [math]4,5[/math] too: the alternative reinforced wheel and its complement.
As before, everything here is self-explanatory, the idea being as follows:
(1-6) Nothing much to be said about these graphs, and their complements.
(7) At valence 3 we have as well the Petersen graph, which is as follows:
This graph seems to appear as some sort of product of the cycle [math]C_5[/math] with the segment [math]C_2[/math], but via a quite complicated procedure. We will be back to this, a bit later.
(8) Nothing much to be said about the two [math]5[/math]-simplices, and its complement, with the computation of the symmetry group here being left for later.
(9) Here there is some discussion to be made, because, contrary to our policy so far, listing graphs with smaller valence than their complements first, here we did the opposite. To start with, the 5-simplex prism, having valence 5, is as follows:
As for the complementary graph to this 5-simplex prism, this is the torch graph, having valence 4, which looks as follows:
(10-11) There is some discussion to be made here, concerning the two possible reinforced wheels on [math]10[/math] vertices, having 2 spokes at each vertex. First we have a reinforced wheel as follows, whose symmetry group is [math]D_{10}[/math], as said in the statement:
But then we have as well the following alternative reinforced wheel, whose symmetry group is a bit more complicated to compute, and we will discuss this later:
Thus, we are led to the conclusions in the statement.
All the above is quite concerning, especially in what concerns the Petersen graph, which looks quite enigmatic. However, before leaving the subject, let us record as well the result at [math]N=11[/math]. Here the order being a small prime, things get again easier:
The transitive graphs at [math]N=11[/math] are as follows:
- Valence [math]0,10[/math]: the empty graph and the simplex, with [math]G(X)=S_{11}[/math].
- Valence [math]2,8[/math]: the hendecagon and its complement, with [math]G(X)=D_{11}[/math].
- Valence [math]4,6[/math]: the reinforced wheel and its complement, with [math]G(X)=D_{11}[/math].
- Valence [math]4,6[/math]: the other reinforced wheel and complement, with [math]G(X)=D_{11}[/math].
Here again business as usual, with the only discussion concerning the two possible reinforced wheels, with 2 spokes at each vertex. A first such wheel is follows:
But then, we have as well a second reinforced wheel, as follows:
Thus, we are led to the conclusions in the statement.
And we will stop here our small [math]N[/math] study, for several reasons:
(1) First of all, because we did some good work in the above, and found many types of graph products, that we have now to investigate in detail.
(2) Second, because of the Petersen graph at [math]N=10[/math], which obviously brings us into uncharted territory, and needs some serious study, before going further.
(3) And third, because at [math]N=12[/math], which is a dazzlingly composite number, things explode, with the number of transitive graphs here being a mighty [math]64[/math].
10c. Standard products
For the transitive graphs, that we are mostly interested in, the point is that, according to the above, at very small values of the order, [math]N=2,\ldots,9[/math], these always decompose as products, via three main types of graph products, constructed as follows:
Let [math]X,Y[/math] be two finite graphs.
- The direct product [math]X\times Y[/math] has vertex set [math]X\times Y[/math], and edges:
[[math]] (i,\alpha)-(j,\beta)\Longleftrightarrow i-j,\, \alpha-\beta [[/math]]
- The Cartesian product [math]X\,\square\,Y[/math] has vertex set [math]X\times Y[/math], and edges:
[[math]] (i,\alpha)-(j,\beta)\Longleftrightarrow i=j,\, \alpha-\beta\mbox{ \rm{or} }i-j,\alpha=\beta [[/math]]
- The lexicographic product [math]X\circ Y[/math] has vertex set [math]X\times Y[/math], and edges:
[[math]] (i,\alpha)-(j,\beta)\Longleftrightarrow\alpha-\beta\mbox{ \rm{or} }\alpha=\beta,\, i-j [[/math]]
Several comments can be made here. First, the direct product [math]X\times Y[/math] is the usual one in a categorical sense, and we will leave clarifying this observation as an exercise. The Cartesian product [math]X\,\square\,Y[/math] is quite natural too from a geometric perspective, for instance because a product by a segment gives a prism. As for the lexicographic product [math]X\circ Y[/math], this is something interesting too, obtained by putting a copy of [math]X[/math] at each vertex of [math]Y[/math].
At the level of symmetry groups, several things can be said, and we first have:
We have group embeddings as follows, for any graphs [math]X,Y[/math],
The fact that we have indeed embeddings as above is clear from definitions. As for the counterexamples, in each case, these are easy to construct as well, provided by our study of small graphs, at [math]N=2,\ldots,11[/math], and we will leave this as an exercise.
The problem now is that of deciding when the embeddings in Theorem 10.14 are isomorphisms. And this is something non-trivial, because there are both examples and counterexamples for these isomorphisms, coming from the various computations of symmetry groups that we did in the above, at [math]N=2,\ldots,11[/math]. We will see, however, that the problem can be solved, via a technical study, of spectral theory flavor.
Now speaking technical algebra and spectral theory, it is good time to go back to the permutation groups [math]G\subset S_N[/math], as introduced and studied in chapter 9, and study them a bit more, from an algebraic perspective. We first have the following basic fact:
Given a subgroup [math]G\subset S_N[/math], regarded as matrix group via
Here the first assertion comes from the fact that the entries of the permutation matrices [math]\sigma\in S_N\subset O_N[/math], acting as [math]\sigma(e_i)=e_{\sigma(i)}[/math], are given by the following formula:
As for the second assertion, this comes from the Stone-Weierstrass theorem, because the coordinate functions [math]u_{ij}:G\to\mathbb C[/math] obviously separate the group elements [math]\sigma\in G[/math].
We are led in this way to the following definition:
The magic matrix associated to a permutation group [math]G\subset S_N[/math] is the [math]N\times N[/math] matrix of characteristic functions
The interest in this notion comes from the fact, that we know from Theorem 10.15, that the entries of the magic matrix generate the algebra of functions on our group:
We will talk more in detail later about such matrices, and their correspondence with the subgroups [math]G\subset S_N[/math], and what can be done with it, in the general framework of representation theory. However, for making our point, here is the general principle:
\begin{principle}
Everything that you can do with your group [math]G\subset S_N[/math] can be expressed in terms of the magic matrix [math]u=(u_{ij})[/math], quite often with good results.
\end{principle}
This principle comes from the above Stone-Weierstrass result, [math]C(G)= \lt u_{ij} \gt [/math]. Indeed, when coupled with some basic spectral theory, and more specifically with the Gelfand theorem from operator algebras, this result tells us that our group [math]G[/math] appears as the spectrum of the algebra [math] \lt u_{ij} \gt [/math], therefore leading to the above principle. But more on this later in this book, when discussing spectral theory, and the Gelfand theorem.
For the moment, we will take Definition 10.16 as it is, something technical of group theory, of rather functional analysis flavor, that we can use in our proofs when needed. And we will take Principle 10.17 also as it is, namely a claim that this is useful indeed.
As an illustration for all this, in relation with the graphs, we have:
Given a subgroup [math]G\subset S_N[/math], the transpose of its action map [math]X\times G\to X[/math] on the set [math]X=\{1,\ldots,N\}[/math], given by [math](i,\sigma)\to\sigma(i)[/math], is given by:
There are several things going on here, the idea being as follows:
(1) Given a subgroup [math]G\subset S_N[/math], if we set [math]X=\{1,\ldots,N\}[/math], we have indeed an action map as follows, and with the reasons of using [math]X\times G[/math] instead of the perhaps more familiar [math]G\times X[/math] being dictated by some quantum algebra, that we will do later in this book:
(2) Now by transposing this map, we obtain a morphism of algebras, as follows:
When evaluated on the Dirac masses, this map [math]\Phi[/math] is then given by:
Thus, in tensor product notation, we have the following formula, as desired:
(3) Regarding now the second assertion, observe first that we have:
On the other hand, we have as well the following formula:
Thus [math]du=ud[/math] reformulates as [math]d_{ij}=d_{\sigma(i)\sigma(j)}[/math], which gives the result.
So long for magic unitaries, and their basic properties, and we will be back to this, on several occasions, in what follows. In fact, the magic matrices will get increasingly important, as the present book develops, because not far away from now, when starting to talk about quantum permutation groups [math]G[/math], and their actions on the graphs [math]X[/math], these beasts will not really exist, as concrete objects [math]G[/math], but their associated magic matrices [math]u=(u_{ij})[/math] will exist, and we will base our whole study on them. More on this later.
Back to graphs now, we want to know when the embeddings in Theorem 10.14 are isomorphisms. In what regards the first two products, we have here the following result, coming with a proof from [1], obtained by using the magic matrix technology:
Let [math]X[/math] and [math]Y[/math] be finite connected regular graphs. If their spectra [math]\{\lambda\}[/math] and [math]\{\mu\}[/math] do not contain [math]0[/math] and satisfy
This is something quite standard, the idea being as follows:
(1) First, we know from Theorem 10.14 that we have embeddings as follows, valid for any two graphs [math]X,Y[/math], and coming from definitions:
(2) Now let [math]\lambda_1[/math] be the valence of [math]X[/math]. Since [math]X[/math] is regular we have [math]\lambda_1\in Sp(X)[/math], with [math]1[/math] as eigenvector, and since [math]X[/math] is connected [math]\lambda_1[/math] has multiplicity 1. Thus if [math]P_1[/math] is the orthogonal projection onto [math]\mathbb C1[/math], the spectral decomposition of [math]d_X[/math] is of the following form:
We have a similar formula for the adjacency matrix [math]d_Y[/math], namely:
(3) But this gives the following formulae for the graph products:
Here the projections form partitions of unity, and the scalar are distinct, so these are spectral decompositions. The coactions will commute with any of the spectral projections, and so with both [math]P_1\otimes1[/math], [math]1\otimes Q_1[/math]. In both cases the universal coaction [math]v[/math] is the tensor product of its restrictions to the images of [math]P_1\otimes1[/math], [math]1\otimes Q_1[/math], which gives the result.
Regarding now the lexicographic product, things here are more tricky. Let us first recall that the lexicographic product of two graphs [math]X\circ Y[/math] is obtained by putting a copy of [math]X[/math] at each vertex of [math]Y[/math], the formula for the edges being as follows:
In what regards now the computation of the symmetry group, as before we must do here some spectral theory, and we are led in this way to the following result:
Let [math]X,Y[/math] be regular graphs, with [math]X[/math] connected. If their spectra [math]\{\lambda_i\}[/math] and [math]\{\mu_j\}[/math] satisfy the condition
This is something quite tricky, the idea being as follows:
(1) First, we know from Theorem 10.14 that we have an embedding as follows, valid for any two graphs [math]X,Y[/math], and coming from definitions:
(2) We denote by [math]P_i,Q_j[/math] the spectral projections corresponding to [math]\lambda_i,\mu_j[/math]. Since [math]X[/math] is connected we have [math]P_1=\mathbb I/n[/math], and we obtain:
In this formula the projections form a partition of unity and the scalars are distinct, so this is the spectral decomposition of [math]d_{X\circ Y}[/math].
(3) Now let [math]W[/math] be the universal magic matrix for [math]X\circ Y[/math]. Then [math]W[/math] must commute with all spectral projections, and in particular:
Summing over [math]j[/math] gives [math][W,P_1\otimes 1]=0[/math], so [math]1\otimes C(Y)[/math] is invariant under the coaction. So, consider the restriction of [math]W[/math], which gives a coaction of [math]G(X\circ Y)[/math] on [math]1\otimes C(Y)[/math], that we can denote as follows, with [math]y[/math] being a certain magic unitary:
(4) On the other hand, according to our definition of [math]W[/math], we can write:
By multiplying by the previous relation, found in (3), we obtain:
But this shows that the coefficients of [math]W[/math] are of the following form:
(5) In order to advance, consider now the following matrix:
Since the map [math]W[/math] above is a morphism of algebras, each row of [math]x^b[/math] is a partition of unity. Also, by using the antipode map [math]S[/math], which is transpose to [math]g\to g^{-1}[/math], we have:
As a conclusion to this, the matrix [math]x^b[/math] constructed above is magic.
(6) We check now that both [math]x^a,y[/math] commute with [math]d_X,d_Y[/math]. We have:
Thus the two products between [math]W[/math] and [math]d_{X\circ Y}[/math] are given by:
(7) Now since the magic matrix [math]W[/math] commutes by definition with [math]d_{X\circ Y}[/math], the terms on the right in the above equations are equal, and by summing over [math]c[/math] we get:
The second sums in both terms are equal to the valence of [math]Y[/math], so we get:
Now once again from the formula coming from [math][W,d_{X\circ Y}]=0[/math], we get:
(8) Summing up, the coefficients of [math]W[/math] are of the following form, where [math]x^b[/math] are magic unitaries commuting with [math]d_X[/math], and [math]y[/math] is a magic unitary commuting with [math]d_Y[/math]:
But this gives a morphism [math]C(G(X)\wr G(Y))\to G(X\circ Y)[/math] mapping [math]u_{ji}^{(b)}\to x_{ji}^b[/math] and [math]v_{ba}\to y_{ba}[/math], which is inverse to the morphism in (1), as desired.
As before with the other graph products, there is some further spectral theory to be done here, plus working out examples. There are as well a number of finer results, for instance the theorem of Sabidussi, to be discussed. We will be back to this.
10d. Kneser graphs
Good news, we have now enough tools in our bag for getting back to the transitive graphs of order [math]N=2,\ldots,11[/math], enumerated and partially studied in the beginning of this chapter, compute the missing symmetry groups there, and end up with a nice table.
Let us begin with some notations, as follows:
We use the following notations for graphs:
- [math]K_N[/math] is the complete graph on [math]N[/math] vertices.
- [math]C_N[/math] is the cycle on [math]N[/math] vertices.
- [math]P(X)[/math] the prism over a graph [math]X[/math].
- [math]C_N^k[/math] is the cycle with chords of length [math]k[/math].
In what regards the transitive graphs of order [math]N=2,\ldots,9[/math], here we have all the symmetry groups already computed, except for 6 of them, which are as follows:
The missing symmetry groups at [math]N\leq9[/math] are as follows:
- For the two triangles [math]2K_3[/math] we obtain [math]S_3\wr\mathbb Z_2[/math].
- For the four segments [math]4K_2[/math] we obtain [math]H_4[/math].
- For the two squares [math]2C_4[/math] we obtain [math]H_2\wr\mathbb Z_2[/math].
- For the two tetrahedra [math]2K_4[/math] we obtain [math]S_4\wr\mathbb Z_2[/math].
- For the three triangles [math]3K_3[/math] we obtain [math]S_3\wr S_3[/math].
- For the torus graph [math]K_3\times K_3[/math] we obtain [math]S_3\wr\mathbb Z_2[/math].
This follows indeed by applying the various product results from the previous section, and we will leave the details here as an instructive exercise.
Regarding the graphs of order [math]N=10,11[/math], things fine at [math]N=11[/math], but at [math]N=10[/math] we have 7 symmetry groups left. The first 6 of them can be computed as follows:
The missing symmetry groups at [math]N=10[/math] are as follows:
- For the five segments [math]5K_2[/math] we obtain [math]H_5[/math].
- For the two pentagons [math]2C_5[/math] we obtain [math]D_5\wr\mathbb Z_2[/math].
- For the pentagon prism [math]P(C_5)[/math] we obtain [math]D_{10}[/math].
- For the two [math]5[/math]-simplices [math]2K_5[/math] we obtain [math]S_5\wr\mathbb Z_2[/math].
- For the [math]5[/math]-simplex prism [math]P(K_5)[/math] we obtain [math]S_5\times\mathbb Z_2[/math].
- For the second reinforced wheel [math]C_{10}^4[/math] we obtain [math]\mathbb Z_2\wr D_5[/math].
This follows too by applying the various product results from the previous section, and we will leave the details here as an instructive exercise.
We have kept the best for the end. Time now to face the only graph left, which is the famous Petersen graph, that we know well since chapter 7, which looks as follows:
Intuition suggests that this graph should appear as a product of the cycle [math]C_5[/math] with the segment [math]C_2[/math]. However, there are many bugs with this idea, which does not work.
In order to view the Petersen graph as part of a larger family, and have some general theory going, we have to proceed in a quite unexpected way, as follows:
The Petersen graph is part of the Kneser graph family,
Consider indeed the Kneser graph [math]K(n,s)[/math], as constructed above. At [math]n=5[/math], [math]s=2[/math] the vertices are the [math]\binom{5}{2}=10[/math] subsets of [math]\{1,\ldots,5\}[/math] having 2 elements, and since each such subset [math]\{p,q\}[/math] is disjoint from exactly 3 other such subsets [math]\{u,v\}[/math], our graph is trivalent, and when drawing the picture, we obtain indeed the Petersen graph.
Many things can be said about the Kneser graphs, and among others, we have:
The Kneser graphs [math]K(n,s)[/math] have the following properties:
- [math]K(n,1)[/math] is the complete graph [math]K_n[/math].
- [math]K(n,2)[/math] is the complement of the line graph [math]L(K_n)[/math].
- [math]K(2m-1,m-1)[/math] is the so-called odd graph [math]O_m[/math].
- The symmetry group of [math]K(n,s)[/math] is the symmetric group [math]S_n[/math].
In particular, [math]P_{10}=K(5,2)=L(K_5)^c=O_3[/math], having symmetry group [math]S_5[/math].
All this is quite self-explanatory, the idea being as follows:
(1) This is something trivial, coming from definitions.
(2) This is clear too from definitions, with the line graph [math]L(X)[/math] of a given graph [math]X[/math] being by definition the incidence graph of the edges of [math]X[/math].
(3) This stands for the definition of [math]O_m[/math], as being the graph [math]K(2m-1,m-1)[/math].
(4) This is clear too, coming from the definition of the Kneser graphs.
All this is very nice, and time to conclude. We have the following table, based on our various results above, containing all transitive graphs up to [math]N=11[/math] vertices, up to complementation, and their symmetry groups, written by using the conventions from Definition 10.21, and with the extra convention that [math]C_n^+[/math] with [math]n[/math] even denote the wheels: \begin{center}\begin{tabular}[t]{|l|l|l|l|}\hline Order&Graph&Symmetry group\\ \hline\hline 2&[math]K_2[/math]&[math]\mathbb Z_2[/math]\\ \hline\hline 3&[math]K_3[/math]&[math]S_3[/math]\\ \hline\hline 4&[math]2K_2[/math]&[math]H_2[/math]\\ \hline 4&[math]K_4[/math]&[math]S_4[/math]\\ \hline\hline 5&[math]C_5[/math]&[math]D_5[/math]\\ \hline5&[math]K_5[/math]&[math]S_5[/math]\\ \hline\hline 6&[math]C_6[/math]&[math]D_6[/math]\\ \hline 6&[math]2K_3[/math]&[math]S_3\wr\mathbb Z_2[/math]\\ \hline 6&[math]3K_2[/math]&[math]H_3[/math]\\ \hline 6&[math]K_6[/math]&[math]S_6[/math]\\ \hline\hline 7&[math]C_7[/math]&[math]D_7[/math]\\ \hline 7&[math]K_7[/math]&[math]S_7[/math]\\ \hline\hline 8&[math]C_8[/math], [math]C_8^+[/math]&[math]D_8[/math]\\ \hline 8&[math]P(C_4)[/math]& [math]H_3[/math]\\ \hline 8&[math]2K_4[/math]&[math]S_4\wr \mathbb Z_2[/math]\\ \hline 8&[math]2C_4[/math]& [math]H_2\wr\mathbb Z_2[/math]\\ \hline 8&[math]4K_2[/math]&[math]H_4[/math]\\ \hline 8&[math]K_8[/math]&[math]S_8[/math]\\ \hline\hline 9&[math]C_9[/math], [math]C_9^3[/math]&[math]D_9[/math]\\ \hline 9 & [math]K_3\times K_3[/math]&[math]S_3\wr\mathbb Z_2[/math]\\ \hline 9&[math]3K_3[/math]&[math]S_3\wr S_3[/math]\\ \hline 9&[math]K_9[/math]&[math]S_9[/math]\\ \hline \hline 10&[math]C_{10}[/math], [math]C_{10}^2[/math], [math]C_{10}^+[/math], [math]P(C_5)[/math]&[math]D_{10}[/math]\\ \hline 10 &[math]P(K_5)[/math]&[math]S_5\times\mathbb Z_2[/math]\\ \hline10&[math]C_{10}^4[/math]&[math]\mathbb Z_2\wr D_5[/math]\\ \hline10&[math]2C_5[/math]&[math]D_5\wr\mathbb Z_2[/math]\\ \hline10&[math]2K_{5}[/math]&[math]S_5\wr\mathbb Z_2[/math]\\ \hline10&[math]5K_2[/math]&[math]H_5[/math]\\ \hline 10&[math]K_{10}[/math]&[math]S_{10}[/math]\\ \hline10&[math]P_{10}[/math]&[math]S_5[/math]\\ \hline\hline 11&[math]C_{11}[/math], [math]C_{11}^2[/math], [math]C_{11}^3[/math]&[math]D_{11}[/math]\\ \hline11&[math]K_{11}[/math]&[math]S_{11}[/math]\\ \hline\end{tabular}\end{center}
Afterwards, at [math]N=12[/math] and higher, the study becomes quite complicated, but we have results for several key series of graphs. We will be back to this, later in this book.
General references
Banica, Teo (2024). "Graphs and their symmetries". arXiv:2406.03664 [math.CO].