Quantum automorphism groups of connected graphs

We have recently uploaded our paper Free Inhomogeneous Wreath Product of Quantum Groups to arXiv. In this paper, we define a new product of (compact matrix) quantum groups and use it to study quantum symmetries of graphs.

Classical picture

How can we determine the automorphism group of a graph in terms of its connected componets? For instance, if $X = K_2 \sqcup K_3$, i.e., $X$ is the disjoint union of $K_2$ and $K_3$, then it is not hard to see that $\text{Aut}(X) = \mathbb{S}_2\times\mathbb{S}_3$; automorphisms act independently on the connected components. If $X = 2K_2 = K_2\sqcup K_2$, the situation is sligthly more involed. See the following figure:

We have two automorphisms that generate $\text{Aut}(2K_2)$: two act independently inside the components and one swaps the connected components. If we look at the diagram of $\text{Aut}(2K_2)$ (on the right), we can intuitively see that this is not a direct product; the front blue-green square is rotated with respect to the back blue-green square and, in a direct product, they should be the same. To calculate the automorphism group in this case, we need a different kind of product, which is called the wreath product.

We need three ingredients needed for a wreath product: a group $G$ and a group $H$ acting on a set $\Omega$ of size $n$. The wreath product of $G\wr_\Omega H$ is simply the semiderect product of $G^n$ by $H$, where $H$ simply acts on the coordinates of $G^n$ in the natural way. Often one just writes $G\wr H$ if $\Omega$ is clear from the context.

We can apply this to the general situation when the graph $X$ is

\[X = \bigsqcup_{i=1}^nk_iX_i,\]

that is, the disjoint union of $k_i$ copies of the graph $X_i$. We have that $\text{Aut}(X)$ is the direct product of wreath prodcuts:

\[\text{Aut}(X) = \prod_{i=1}^n\text{Aut}(X_i)\wr\mathbb{S}_{k_i}.\]

How can we determine the automorphism group of a connected graph from its biconnected components? The idea is to consider the block tree of a graph $X$, which is the incidence graph of the biconnected components of $X$ and its cut vertices.