guide:F83d45e58a

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

Generally speaking, the graphs having small number of vertices can be investigated by using product operations plus complementation. The first graph which is resistent to such a study is the torus graph [math]K_3\times K_3[/math], but we have here, following :

Theorem

The torus graph, obtained as a product of a triangle with itself,

[[math]] X=K_3\times K_3 [[/math]]

has no quantum symmetry, [math]G^+(X)=G(X)=S_3\wr\mathbb Z_2[/math].

Show Proof

This is something quite tricky, the idea being as follows:

(1) To start with, we have [math]Sp(X)=\{-2,1,4\}[/math], the corresponding eigenspaces being as follows, with [math]\xi_{ij}=\xi^i\otimes \xi^j[/math], where [math]\xi=(1,w,w^2)[/math], with [math]w=e^{2\pi i/3}[/math]:

[[math]] E_{-2}=\mathbb C\xi_{10}\oplus\mathbb C\xi_{01}\oplus\mathbb C\xi_{20}\oplus\mathbb C\xi_{02} [[/math]]

[[math]] E_1=\mathbb C\xi_{11}\oplus\mathbb C\xi_{12}\oplus\mathbb C\xi_{21}\oplus\mathbb C\xi_{22} [[/math]]

[[math]] E_4=\mathbb C\xi_{00} [[/math]]

(2) Since the universal coaction [math]v:C(X)\to C(X)\otimes A[/math] preserves the eigenspaces, we can write formulae as follows, for some [math]a,b,c,d,\alpha,\beta,\gamma,\delta \in A[/math]:

[[math]] v(\xi_{10})=\xi_{10}\otimes a+\xi_{01}\otimes b+\xi_{20}\otimes c+\xi_{02}\otimes d [[/math]]

[[math]] v(\xi_{01})=\xi_{10}\otimes\alpha+\xi_{01}\otimes\beta+\xi_{20}\otimes\gamma+\xi_{02}\otimes\delta [[/math]]

Taking the square of [math]v(\xi_{10})[/math] gives the following formula:

[[math]] v(\xi_{20})=\xi_{20}\otimes a^2+\xi_{02}\otimes b^2+\xi_{10}\otimes c^2+\xi_{01}\otimes d^2 [[/math]]

Also, from eigenspace preservation, we have the following relations:

[[math]] ab=-ba\ , \ ad=-da\ , \ bc=-cb\ , \ cd=-dc [[/math]]

[[math]] ac+ca=-(bd+db) [[/math]]

(3) Now since [math]a,b[/math] anticommute, their squares have to commute. On the other hand, by applying [math]v[/math] to the equality [math]\xi_{10}^*=\xi_{20}[/math], we get the following formulae for adjoints:

[[math]] a^*=a^2\ , \ b^*=b^2\ , \ c^*=c^2\ , \ d^*=d^2 [[/math]]

The commutation relation [math]a^2b^2=b^2a^2[/math] reads now [math]a^*b^*=b^*a^*[/math], and by taking adjoints we get [math]ba=ab[/math]. Together with [math]ab=-ba[/math] this gives:

[[math]] ab=ba=0 [[/math]]

The same method applies to [math]ad,bc,cd[/math], and we end up with:

[[math]] ab=ba=0\ ,\ ad=da =0\ , \ bc=cb =0\ , \ cd=dc=0 [[/math]]

(4) We apply now [math]v[/math] to the equality [math]1=\xi_{10}\xi_{20}[/math]. We get that [math]1[/math] is the sum of [math]16[/math] terms, all of them of the form [math]\xi_{ij}\otimes P[/math], where [math]P[/math] are products between [math]a,b,c,d[/math] and their squares. Due to the above formulae 8 terms vanish, and the [math]8[/math] remaining ones give:

[[math]] 1=a^3 +b^3 +c^3 +d^3 [[/math]]

We have as well the relations coming from eigenspace preservation, namely:

[[math]] ac^2=ca^2=bd^2=db^2=0 [[/math]]

(5) Now from [math]ac^2=0[/math] we get [math]a^2c^2=0[/math], and by taking adjoints this gives [math]ca=0[/math]. The same method applies to [math]ac,bd,db[/math], and we end up with:

[[math]] ac=ca=0\ ,\ bd=db=0 [[/math]]

In the same way we can show that [math]\alpha,\beta,\gamma,\delta[/math] pairwise commute:

[[math]] \alpha\beta=\beta\alpha=\ldots =\gamma\delta=\delta\gamma=0 [[/math]]

(6) In order to finish the proof, it remains to show that [math]a,b,c,d[/math] commute with [math]\alpha,\beta,\gamma,\delta[/math]. For this purpose, we apply [math]v[/math] to the following equality:

[[math]] \xi_{10}\xi_{01}=\xi_{01}\xi_{10} [[/math]]

We obtain in this way an equality between two sums having 16 terms each, and by using again the eigenspace preservation condition we get the following formulae relating the corresponding 32 products [math]a\alpha,\alpha a[/math], and so on:

[[math]] a\alpha=\alpha a=0\quad,\quad b\beta=\beta b=0 [[/math]]

[[math]] c\gamma=\gamma c=0\quad,\quad d\delta=\delta d=0 [[/math]]

[[math]] a\gamma+c\alpha+b\delta+d\beta=0\quad,\quad \alpha c+\gamma a+\beta d+\delta b=0 [[/math]]

[[math]] a\beta+b\alpha=\alpha b+\beta a\quad,\quad b\gamma+c\beta=\beta c+\gamma b [[/math]]

[[math]] c\delta+d\gamma=\gamma d+\delta c\quad,\quad a\delta+d\alpha=\alpha d+\delta a [[/math]]

(7) Now observe that multiplying the first equality in the third row on the left by [math]a[/math] and on the right by [math]\gamma[/math] gives [math]a^2\gamma^2 =0[/math], and by taking adjoints we get [math]\gamma a=0[/math]. The same method applies to the other 7 products involved in the third row, so all 8 products involved in the third row vanish. That is, we have the following formulae:

[[math]] a\gamma=c\alpha=b\delta=d\beta=\alpha c=\gamma a=\beta d=\delta b=0 [[/math]]

(8) We use now the first equality in the fourth row. Multiplying it on the left by [math]a[/math] gives [math]a^2\beta=a\beta a[/math], and multiplying it on the right by [math]a[/math] gives [math]a\beta a=\beta a^2[/math]. Thus we get [math]a^2\beta=\beta a^2[/math]. On the other hand from [math]a^3+b^3+c^3+d^3=1[/math] we get [math]a^4=a[/math], so:

[[math]] a\beta=a^4 \beta=a^2a^2 \beta=\beta a^2a^2=\beta a [[/math]]

Finally, one can show in a similar manner that the missing commutation formulae [math]a\delta = \delta a[/math] and so on, hold as well. Thus the algebra [math]A[/math] is commutative, as desired.

■

As a second graph which is resistent to a routine product study, we have the Petersen graph [math]P_{10}[/math]. In order to explain the computation here, done by Schmidt in , we will need a number of preliminaries. Let us start with the following notion, from :

Definition

The reduced quantum automorphism group of [math]X[/math] is given by

[[math]] C(G^*(X))=C(G^+(X))\Big/\left \lt u_{ij}u_{kl}=u_{kl}u_{ij}\Big|\forall i-k,j-l\right \gt [[/math]]

with [math]i-j[/math] standing as usual for the fact that [math]i,j[/math] are connected by an edge.

As explained by Bichon in , the above construction produces indeed a quantum group [math]G^*(X)[/math], which sits as an intermediate subgroup, as follows:

[[math]] G(X)\subset G^*(X)\subset G^+(X) [[/math]]

There are many things that can be said about this construction, but in what concerns us, we will rather use it as a technical tool. Following Schmidt , we have:

Proposition

Assume that a regular graph [math]X[/math] is strongly regular, with parameters [math]\lambda=0[/math] and [math]\mu=1[/math], in the sense that:

• [math]i-j[/math] implies that [math]i,j[/math] have [math]\lambda[/math] common neighbors.
• [math]i\not\!\!-\,j[/math] implies that [math]i,j[/math] have [math]\mu[/math] common neighbors.

The quantum group inclusion [math]G^*(X)\subset G^+(X)[/math] is then an isomorphism.

Show Proof

This is something quite tricky, the idea being as follows:

(1) First of all, regarding the statement, a graph is called regular, with valence [math]k[/math], when each vertex has exactly [math]k[/math] neighbors. Then we have the notion of strong regularity, given by the conditions (1,2) in the statement. And finally we have the notion of strong regularity with parameters [math]\lambda=0,\mu=1[/math], that the statement is about, and with as main example here [math]P_{10}[/math], which is 3-regular, and strongly regular with [math]\lambda=0,\mu=1[/math].

(2) Regarding now the proof, we must prove that the following commutation relation holds, with [math]u[/math] being the magic unitary of the quantum group [math]G^+(X)[/math]:

[[math]] u_{ij}u_{kl}=u_{kl}u_{ij}\ ,\ \forall i-k,j-l [[/math]]

(3) But for this purpose, we can use the [math]\lambda=0,\mu=1[/math] strong regularity of our graph, by inserting some neighbors into our computation. To be more precise, we have:

[[math]] \begin{eqnarray*} u_{ij}u_{kl} &=&u_{ij}u_{kl}\sum_{s-l}u_{is}\\ &=&u_{ij}u_{kl}u_{ij}+\sum_{s-l,s\neq j}u_{ij}u_{kl}u_{is}\\ &=&u_{ij}u_{kl}u_{ij}+\sum_{s-l,s\neq j}u_{ij}\left(\sum_au_{ka}\right)u_{is}\\ &=&u_{ij}u_{kl}u_{ij}+\sum_{s-l,s\neq j}u_{ij}u_{is}\\ &=&u_{ij}u_{kl}u_{ij} \end{eqnarray*} [[/math]]

(4) But this gives the result. Indeed, we conclude from this that [math]u_{ij}u_{kl}[/math] is self-adjoint, and so, by conjugating, that we have [math]u_{ij}u_{kl}=u_{kl}u_{ij}[/math], as desired.

■

In the particular case of the Petersen graph [math]P_{10}[/math], which in addition is 3-regular, we can further build on the above result, and still following Schmidt , we have:

Theorem

The Petersen graph has no quantum symmetry,

[[math]] G^+(P_{10})=G(P_{10})=S_5 [[/math]]

with [math]S_5[/math] acting in the obvious way.

Show Proof

In view of Proposition 14.36, we must prove that the following commutation relation holds, with [math]u[/math] being the magic unitary of the quantum group [math]G^+(P_{10})[/math]:

[[math]] u_{ij}u_{kl}=u_{kl}u_{ij}\ ,\ \forall i\not\!\!-\,k,j\not\!\!-\,l [[/math]]

We can assume [math]i\neq k[/math], [math]j\neq l[/math]. Now if we denote by [math]s,t[/math] the unique vertices having the property [math]i-s,k-s[/math] and [math]j-t,l-t[/math], a routine study shows that we have:

[[math]] u_{ij}u_{kl}=u_{ij}u_{st}u_{kl} [[/math]]

With this in hand, if we denote by [math]q[/math] the third neighbor of [math]t[/math], we obtain:

[[math]] \begin{eqnarray*} u_{ij}u_{kl} &=&u_{ij}u_{st}u_{kl}(u_{ij}+u_{il}+u_{iq})\\ &=&u_{ij}u_{st}u_{kl}u_{ij}+0+0\\ &=&u_{ij}u_{st}u_{kl}u_{ij}\\ &=&u_{ij}u_{kl}u_{ij} \end{eqnarray*} [[/math]]

Thus the element [math]u_{ij}u_{kl}[/math] is self-adjoint, and we obtain, as desired:

[[math]] u_{ij}u_{kl}=u_{kl}u_{ij} [[/math]]

As for the fact that the usual symmetry group is [math]S_5[/math], this is something that we know well from chapter 10, coming from the Kneser graph picture of [math]P_{10}[/math].

■

As an application of this, we have the following classification table from , improved by using , containing all the vertex-transitive graphs of order [math]\leq 11[/math] modulo complementation, with their classical and quantum symmetry groups: \begin{center}\begin{tabular}[t]{|l|l|l|l|} \hline Order&Graph&Classical group&Quantum group\\ \hline\hline 2&[math]K_2[/math]&[math]\mathbb Z_2[/math]&[math]\mathbb Z_2[/math]\\ \hline\hline 3&[math]K_3[/math]&[math]S_3[/math]&[math]S_3[/math]\\ \hline\hline 4&[math]2K_2[/math]&[math]H_2[/math]&[math]H_2^+[/math]\\ \hline 4&[math]K_4[/math]&[math]S_4[/math]&[math]S_4^+[/math]\\ \hline\hline 5&[math]C_5[/math]&[math]D_5[/math]&[math]D_5[/math]\\ \hline5&[math]K_5[/math]&[math]S_5[/math]&[math]S_5^+[/math]\\ \hline\hline 6&[math]C_6[/math]&[math]D_6[/math]&[math]D_6[/math]\\ \hline 6&[math]2K_3[/math]&[math]S_3\wr\mathbb Z_2[/math]&[math]S_3{\,\wr_*\,}\mathbb Z_2[/math]\\ \hline 6&[math]3K_2[/math]&[math]H_3[/math]&[math]H_3^+[/math]\\ \hline 6&[math]K_6[/math]&[math]S_6[/math]&[math]S_6^+[/math]\\ \hline\hline 7&[math]C_7[/math]&[math]D_7[/math]&[math]D_7[/math]\\ \hline7&[math]K_7[/math]&[math]S_7[/math]&[math]S_7^+[/math]\\ \hline\hline 8&[math]C_8[/math], [math]C_8^+[/math]&[math]D_8[/math]&[math]D_8[/math]\\ \hline 8&[math]P(C_4)[/math]& [math]H_3[/math]&[math]S_4^+\times \mathbb Z_2[/math]\\ \hline 8&[math]2K_4[/math]&[math]S_4\wr \mathbb Z_2[/math]&[math]S_4^+{\,\wr_*\,}\mathbb Z_2[/math]\\ \hline 8&[math]2C_4[/math]& [math]H_2\wr\mathbb Z_2[/math] & [math]H_2^+{\,\wr_*\,}\mathbb Z_2[/math]\\ \hline 8&[math]4K_2[/math]&[math]H_4[/math]&[math]H_4^+[/math] \\ \hline 8&[math]K_8[/math]&[math]S_8[/math]&[math]S_8^+[/math]\\ \hline\hline 9&[math]C_9[/math], [math]C_9^3[/math]&[math]D_9[/math]&[math]D_9[/math]\\ \hline 9 & [math]K_3\times K_3[/math]&[math]S_3\wr\mathbb Z_2[/math]&[math]S_3\wr\mathbb Z_2[/math]\\ \hline 9&[math]3K_3[/math]&[math]S_3\wr S_3[/math]&[math]S_3{\,\wr_*\,}S_3[/math]\\ \hline9&[math]K_9[/math]&[math]S_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]&[math]D_{10}[/math]\\ \hline 10 &[math]P(K_5)[/math]&[math]S_5\times\mathbb Z_2[/math]&[math]S_5^+\times\mathbb Z_2[/math]\\ \hline10&[math]C_{10}^4[/math]&[math]\mathbb Z_2\wr D_5[/math]&[math]\mathbb Z_2{\,\wr_*\,}D_5[/math]\\ \hline10&[math]2C_5[/math]&[math]D_5\wr\mathbb Z_2[/math]&[math]D_5{\,\wr_*\,}\mathbb Z_2[/math]\\ \hline10&[math]2K_{5}[/math]&[math]S_5\wr\mathbb Z_2[/math]&[math]S_5^+{\,\wr_*\,}\mathbb Z_2[/math]\\ \hline10&[math]5K_2[/math]&[math]H_5[/math]&[math]H_5^+[/math]\\ \hline10&[math]K_{10}[/math]&[math]S_{10}[/math]&[math]S_{10}^+[/math]\\ \hline10&[math]P_{10}[/math]&[math]S_5[/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]&[math]D_{11}[/math]\\ \hline11&[math]K_{11}[/math]&[math]S_{11}[/math]&[math]S_{11}^+[/math]\\ \hline \end{tabular}\end{center} Here [math]K[/math] denote the complete graphs, [math]C[/math] the cycles with chords, and [math]P[/math] stands for prisms. Moreover, by using more advanced techniques, the above table can be considerably extended. For more on all this, we refer to Schmidt's papers , , .

General references

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