14b. Product operations

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

We would like to understand how the operation [math]X\to G^+(X)[/math] behaves under taking various products of graphs, in analogy with what we know about [math]X\to G(X)[/math], from chapter 10. As a first observation, things can be quite tricky here, as shown by: \begin{fact} Although the graph formed by two points [math]\bullet\,\bullet[/math] has no quantum symmetry, the graph formed by two copies of it, namely [math]\bullet\,\bullet\,\bullet\,\,\bullet[/math]\,, does have quantum symmetry. \end{fact} Which looks quite scary, but no worries, we will manage to reach to a better understanding of this. Getting to work now, let us recall from chapter 10 that we have:

Definition

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]]

The above products are all well-known in graph theory, and we have already studied them in chapter 10, in relation with symmetry groups, with the following conclusion:

Theorem

We have standard embeddings, as follows,

[[math]] G(X)\times G(Y)\subset G(X \times Y) [[/math]]

[[math]] G(X)\times G(Y)\subset G(X\,\square\,Y) [[/math]]

[[math]] G(X)\wr G(Y)\subset G(X\circ Y) [[/math]]

and under suitable spectral assumptions, these embeddings are isomorphisms.

Show Proof

This is something that we know from chapter 10, and we refer to the discussion there for both the precise statement of the last assertion, and for the proofs.

■

In order to discuss the quantum analogues of these embeddings, we need to introduce first a number of operations on the compact quantum groups, similar to the above operations for the finite groups. Following Wang , we first have:

Proposition

Given two compact quantum groups [math]G,H[/math], so is their product [math]G\times H[/math], constructed according to the following formula:

[[math]] C(G\times H)=C(G)\otimes C(H) [[/math]]

Equivalently, at the level of the associated discrete duals [math]\Gamma,\Lambda[/math], we can set

[[math]] C^*(\Gamma\times\Lambda)=C^*(\Gamma)\otimes C^*(\Lambda) [[/math]]

and we obtain the same equality of Woronowicz algebras as above.

Show Proof

Assume indeed that we have two Woronowicz algebras, [math](A,u)[/math] and [math](B,v)[/math]. Our claim is that the following construction produces a Woronowicz algebra:

[[math]] C=A\otimes B\quad,\quad w=diag(u,v) [[/math]]

Indeed, the matrix [math]w[/math] is unitary, and its coefficients generate [math]C[/math]. As for the existence of the maps [math]\Delta,\varepsilon,S[/math], this follows from the functoriality properties of [math]\otimes[/math]. But with this claim in hand, the first assertion is clear. As for the second assertion, let us recall that when [math]G,H[/math] are classical and abelian, we have the following formula:

[[math]] \widehat{G\times H}=\widehat{G}\times\widehat{H} [[/math]]

Thus, our second assertion is simply a reformulation of the first assertion, with the [math]\times[/math] symbol used there being justified by this well-known group theory formula.

■

Another standard operation, again from , is that of taking subgroups:

Proposition

Let [math]G[/math] be compact quantum group, and let [math]I\subset C(G)[/math] be a closed [math]*[/math]-ideal satisfying the following condition:

[[math]] \Delta(I)\subset C(G)\otimes I+I\otimes C(G) [[/math]]

We have then a closed quantum subgroup [math]H\subset G[/math], constructed as follows:

[[math]] C(H)=C(G)/I [[/math]]

At the dual level we obtain a quotient of discrete quantum groups, [math]\widehat{\Gamma}\to\widehat{\Lambda}[/math].

Show Proof

This follows indeed from the above conditions on [math]I[/math], which are designed precisely as for [math]\Delta,\varepsilon,S[/math] to factorize through the quotient. As for the last assertion, this is just a reformulation, coming from the functoriality properties of the Pontrjagin duality.

■

Regarding now taking quotients, the result here, again from , is as follows:

Proposition

Let [math]G[/math] be a compact quantum group, and [math]v=(v_{ij})[/math] be a corepresentation of [math]C(G)[/math]. We have then a quotient quantum group [math]G\to H[/math], given by:

[[math]] C(H)= \lt v_{ij} \gt [[/math]]

At the dual level we obtain a discrete quantum subgroup, [math]\widehat{\Lambda}\subset\widehat{\Gamma}[/math].

Show Proof

Here the first assertion follows from definitions, and the second assertion is a reformulation of it, using the basic properties of Pontrjagin duality.

■

Finally, we will need the notion of free wreath product, from , as follows:

Proposition

Given closed subgroups [math]G\subset S_N^+[/math], [math]H\subset S_k^+[/math], with magic corepresentations [math]u,v[/math], the following construction produces a closed subgroup of [math]S_{Nk}^+[/math]:

[[math]] C(G\wr_*H)=(C(G)^{*k}*C(H))/ \lt [u_{ij}^{(a)},v_{ab}]=0 \gt [[/math]]

When [math]G,H[/math] are classical, the classical version of [math]G\wr_*H[/math] is the wreath product [math]G\wr H[/math].

Show Proof

Consider indeed the matrix [math]w_{ia,jb}=u_{ij}^{(a)}v_{ab}[/math], over the quotient algebra in the statement. Our claim is that this matrix is magic. Indeed, the entries are projections, because they appear as products of commuting projections, and the row sums are:

[[math]] \sum_{jb}w_{ia,jb} =\sum_{jb}u_{ij}^{(a)}v_{ab} =\sum_bv_{ab}\sum_ju_{ij}^{(a)} =1 [[/math]]

As for the column sums, these are as follows:

[[math]] \sum_{ia}w_{ia,jb} =\sum_{ia}u_{ij}^{(a)}v_{ab} =\sum_av_{ab}\sum_iu_{ij}^{(a)} =1 [[/math]]

With this in hand, it is routine to check that [math]G\wr_*H[/math] is indeed a quantum permutation group. Finally, the last assertion is standard as well. See .

■

With the above discussed, we can now go back to graphs. Following , the standard embeddings from Theorem 14.10 have the following quantum analogues:

Theorem

We have embeddings as follows,

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

[[math]] G^+(X)\times G^+(Y)\subset G^+(X\,\square\,Y) [[/math]]

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

with the operation [math]\wr_*[/math] being a free wreath product.

Show Proof

We use the following identification, given by [math]\delta_{(i,\alpha)}=\delta_i\otimes\delta_\alpha[/math]:

[[math]] C(X\times Y)=C(X)\otimes C(Y) [[/math]]

(1) The adjacency matrix of the direct product is given by:

[[math]] d_{X\times Y}=d_X\otimes d_Y [[/math]]

Thus if [math]u[/math] commutes with [math]d_X[/math] and [math]v[/math] commutes with [math]d_Y[/math], then [math]u\otimes v=(u_{ij}v_{\alpha\beta})_{(i\alpha,j\beta)}[/math] is a magic unitary that commutes with [math]d_{X\times Y}[/math]. But this gives a morphism as follows:

[[math]] C(G^+(X\times Y))\to C(G^+(X)\times G^+(Y)) [[/math]]

Finally, the surjectivity of this morphism follows by summing over [math]i[/math] and [math]\beta[/math].

(2) The adjacency matrix of the Cartesian product is given by:

[[math]] d_{X\,\square\,Y}=d_X\otimes1+1\otimes d_Y [[/math]]

Thus if [math]u[/math] commutes with [math]d_X[/math] and [math]v[/math] commutes with [math]d_Y[/math], then [math]u\otimes v=(u_{ij}v_{\alpha\beta})_{(i\alpha,j\beta)}[/math] is a magic unitary that commutes with [math]d_{X\,\square\,Y}[/math], and this gives the result.

(3) The adjacency matrix of the lexicographic product [math]X\circ Y[/math] is given by:

[[math]] d_{X\circ Y}=d_X\otimes1+\mathbb I\otimes d_Y [[/math]]

Now let [math]u,v[/math] be the magic unitary matrices of [math]G^+(X),G^+(Y)[/math]. The magic unitary matrix of [math]G^+(X)\wr_*G^+(Y)[/math] is then given by the following formula:

[[math]] w_{ia,jb}= u_{ij}^{(a)}v_{ab} [[/math]]

Since [math]u,v[/math] commute with [math]d_X,d_Y[/math], we get that [math]w[/math] commutes with [math]d_{X\circ Y}[/math]. But this gives the desired morphism, and the surjectivity follows by summing over [math]i[/math] and [math]b[/math].

■

The problem now is that of deciding when the embeddings in Theorem 14.15 are isomorphisms. Following , we first have the following result:

Theorem

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

[[math]] \big\{\lambda_i/\lambda_j\big\}\cap\big\{\mu_k/\mu_l\big\}=\{1\} [[/math]]

then [math]G^+(X\times Y)=G^+(X)\times G^+(Y)[/math]. Also, if their spectra satisfy

[[math]] \big\{\lambda_i-\lambda_j\big\}\cap\big\{\mu_k-\mu_l\big\}=\{0\} [[/math]]

then [math]G^+(X\,\square\,Y)=G^+(X)\times G^+(Y)[/math].

Show Proof

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

(1) First, we know from Theorem 14.15 that we have embeddings as follows, valid for any two graphs [math]X,Y[/math], and coming from definitions:

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

[[math]] G^+(X)\times G^+(Y)\subset G^+(X\,\square\,Y) [[/math]]

(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. Hence 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:

[[math]] d_X=\lambda_1P_1+\sum_{i\neq1}\lambda_iP_i [[/math]]

We have a similar formula for the adjacency matrix [math]d_Y[/math], namely:

[[math]] d_Y=\mu_1Q_1+\sum_{j\neq1}\mu_jQ_j [[/math]]

(3) But this gives the following formulae for products:

[[math]] d_{X\times Y}=\sum_{ij}(\lambda_i\mu_j)P_{i}\otimes Q_{j} [[/math]]

[[math]] d_{X\,\square\,Y}=\sum_{ij}(\lambda_i+\mu_i)P_i\otimes Q_j [[/math]]

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 hence 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 products, the result here is as follows:

Theorem

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

[[math]] \big\{\lambda_1-\lambda_i\big|i\neq 1\big\}\cap\big\{-n\mu_j\big\}=\emptyset [[/math]]

where [math]n[/math] and [math]\lambda_1[/math] are the order and valence of [math]X[/math], then [math]G^+(X\circ Y)=G^+(X)\wr_*G^+(Y)[/math].

Show Proof

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

(1) First, we know from Theorem 14.15 that we have an embedding as follows, valid for any two graphs [math]X,Y[/math], and coming from definitions:

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

(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:

[[math]] \begin{eqnarray*} d_{X\circ Y} &=&d_X\otimes 1+{\mathbb I}\otimes d_Y\\ &=&\left(\sum_i\lambda_iP_i\right)\otimes\left(\sum_jQ_j\right)+\left(nP_1\right)\otimes \left(\sum_i\mu_jQ_j\right)\\ &=&\sum_j(\lambda_1+n\mu_j)(P_1\otimes Q_j) + \sum_{i\not=1}\lambda_i(P_i\otimes 1) \end{eqnarray*} [[/math]]

Since in this formula the projections form a partition of unity, and the scalars are distinct, we conclude that 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, we have:

[[math]] [W,P_1\otimes Q_j]=0 [[/math]]

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:

[[math]] W(1\otimes e_a)=\sum_b1\otimes e_b\otimes y_{ba} [[/math]]

(4) On the other hand, according to our definition of [math]W[/math], we can write:

[[math]] W(e_i\otimes 1)=\sum_{jb}e_j\otimes e_b\otimes x_{ji}^b [[/math]]

By multiplying by the previous relation, found in (3), we obtain:

[[math]] W(e_i\otimes e_a) =\sum_{jb}e_j\otimes e_b\otimes y_{ba}x_{ji}^b =\sum_{jb}e_j \otimes e_b\otimes x_{ji}^by_{ba} [[/math]]

But this shows that the coefficients of [math]W[/math] are of the following form:

[[math]] W_{jb,ia}=y_{ba}x_{ji}^b=x_{ji}^b y_{ba} [[/math]]

(5) Consider now the matrix [math]x^b=(x_{ij}^b)[/math]. Since [math]W[/math] is a morphism of algebras, each row of [math]x^b[/math] is a partition of unity. Also, by using the antipode, we have:

[[math]] S\left(\sum_jx_{ji}^{b}\right) =S\left(\sum_{ja}W_{jb,ia}\right) =\sum_{ja}W_{ia,jb} =1 [[/math]]

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:

[[math]] (d_{X\circ Y})_{ia,jb} = (d_X)_{ij}\delta_{ab} + (d_Y)_{ab} [[/math]]

Thus the two products between [math]W[/math] and [math]d_{X\circ Y}[/math] are given by:

[[math]] (Wd_{X\circ Y})_{ia,kc}=\sum_j W_{ia,jc} (d_X)_{jk} + \sum_{jb}W_{ia,jb}(d_Y)_{bc} [[/math]]

[[math]] (d_{X\circ Y}W)_{ia,kc}=\sum_j (d_X)_{ij} W_{ja,kc} + \sum_{jb}(d_Y)_{ab}W_{jb,kc} [[/math]]

(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:

[[math]] \sum_j x_{ij}^a(d_X)_{jk} + \sum_{cb} y_{ab}(d_Y)_{bc} = \sum_{j} (d_X)_{ij}x_{jk}^a + \sum_{cb} (d_Y)_{ab}y_{bc} [[/math]]

The second sums in both terms are equal to the valence of [math]Y[/math], so we get:

[[math]] [x^a,d_X]=0 [[/math]]

Now once again from the formula coming from [math][W,d_{X\circ Y}]=0[/math], we get:

[[math]] [y,d_Y] =0 [[/math]]

(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]:

[[math]] W_{jb,ia}=x_{ji}^by_{ba} [[/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 a main application of the above result, we have:

Theorem

Given a connected graph [math]X[/math], and [math]k\in\mathbb N[/math], we have the formulae

[[math]] G(kX)=G(X)\wr S_k\quad,\quad G^+(kX)=G^+(X)\wr_*S_k^+ [[/math]]

where [math]kX=X\sqcup\ldots\sqcup X[/math] is the [math]k[/math]-fold disjoint union of [math]X[/math] with itself.

Show Proof

The first formula is something well-known, which follows as well from the second formula, by taking the classical version. Regarding now the second formula, it is elementary to check that we have an inclusion as follows, for any finite graph [math]X[/math]:

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

Regarding now the reverse inclusion, which requires [math]X[/math] to be connected, this follows by doing some matrix analysis, by using the commutation with [math]u[/math]. To be more precise, let us denote by [math]w[/math] the fundamental corepresentation of [math]G^+(kX)[/math], and set:

[[math]] u_{ij}^{(a)}=\sum_bw_{ia,jb}\quad,\quad v_{ab}=\sum_iv_{ab} [[/math]]

It is then routine to check, by using the fact that [math]X[/math] is indeed connected, that we have here magic unitaries, as in the definition of the free wreath products. Thus, we obtain:

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

But this gives the result, as a consequence of Theorem 14.17. See .

■

We refer to and related papers for further results, along these lines.

General references

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