Some notes on this paper.

### 1. Introduction and Main Results

A tree has no symmetry if its automorphism group is trivial. Erdos and Rényi showed that the probability that a random tree on $n$ vertices has no symmetry goes to zero as $n\rightarrow \infty$.

Banica (after Bichon) wrote down with clarity the quantum automorphism group of a graph. It contains the usual automorphism group. When it is larger, the graph is said to have quantum symmetry.

Lupini, Mancinska, and Roberson show that almost all graphs are quantum antisymmetric. I am fairly sure this means that almost all graphs have no quantum symmetry, and furthermore for almost all (as $n\rightarrow \infty$) graphs the automorphism group is trivial.

The paper in question hopes to show that almost all trees have quantum symmetry — but at this point I am not sure if this is saying that the quantum automorphism group is larger than the classical.

## 2. Preliminaries

### 2.1 Graphs and Trees

Standard definitions. No multi-edges. Undirected if the edge relation is symmetric. As it is dealing with trees, this paper is concerned with undirected graphs without loops, and identify $V=\{v_1,\dots,v_n\}\cong \{1,2,\dots,n\}$. A path is a sequence of edges. We will not see cycles if we are discussing trees. Neither will we talk about disconnected graphs: a tree is a connected graph without cycles (this throws out loops actually.

The adjacency matrix of a graph is a matrix $A=(a_{ik})_{i,j\in V}$ with $a_{ij}=1$ iff there is an edge connected $i$ and $j$. The adjacency matrix is symmetric.

### 2.2 Symmetries of Graphs

An automorphism of a graph $\Gamma$ is a permutation of $V$ that preserves adjacency and non-adjacency. The set of all such automorphisms, $\text{Aut }\Gamma$, is a group where the group law is composition. It is a subgroup of $S_n$, and $S_n$ itself can be embedded as permutation matrices in $M_n(\mathbb{C})$. We then have

$\text{Aut }\Gamma=\{\sigma\in S_n\,:\,\sigma A=A\sigma\}\subseteq S_n$.

If $\text{Aut }\Gamma=\{e\}$, it is asymmetric. Otherwise it is or rather has symmetry.

### 2.3 Compact Matrix Quantum Groups

compact matrix quantum group is a pair $(C(G),u)$, where $C(G)$ is a unital $\mathrm{C}^\ast$-algebra, and $u=(u_{ij})_{i,j=1}^n\in M_n(C(G))$ is such that:

• $C(G)$ is generated by the $u_{ij}$,
• There exists a morphism $\Delta:C(G)\rightarrow C(G)\otimes C(G)$, such that $\Delta(u_{ij})=\sum_{k=1}^n u_{ik}\otimes u_{kj}$
• $u$ and $u^T$ are invertible (Timmermann only asks that $\overline{u}=(u_{ij}^\ast)$ be invertible)

The classic example (indeed commutative examples all take this form) is a compact matrix group $G\subseteq U_n(\mathbb{C})$ and $u_{ij}:G\rightarrow \mathbb{C}$ the coordinates of $G$.

#### Example 2.3

The algebra of continuous functions on the quantum permutation group $S_n^+$ is generated by $n^2$ projections $u_{ij}$ such that the row sums and column sums of $u=(u_{ij})$ both equal $\mathbf{1}_{S_n^+}$.

The map $\varphi:C(S_{n}^+)\rightarrow C(S_n)$, $u_{ij}\mapsto \mathbf{1}_{\{\sigma\in S_n\,|\,\sigma(j)=i\}}$ is a surjective morphism that is an isomorphism for $n=1,2,3$, so that the sets $\{1\},\,\{1,2\},\,\{1,2,3\}$ have no quantum symmetries.

### 2.4 Quantum Symmetries of Graphs

#### Definition 2.4 (Banica after Bichon)

Let $\Gamma=(V,E)$ be a graph on $n$ vertices without multiple edges not loops, and let $A$ be its adjacency matrix. The quantum automorphism group $\text{QAut }\Gamma$ is defined as the compact matrix group with $\mathrm{C}^\ast$-algebra:

$\displaystyle C(\text{QAut }\Gamma)=C(S_n^+)/\langle uA=Au\rangle$

For me, not the authors, this requires some work. Banica says that $\langle uA=Au\rangle$ is a Hopf ideal.

Hopf ideal is a closed *-ideal $I\subset C(G)$ such that

$\Delta(I)\subset C(G)\otimes I+I\otimes C(G)$.

Classically, $I$ the set of functions vanishing on a distinguished subgroup. The quotient map is $f\mapsto f+I$, and $f+I=g+I$ if their difference is in $I$, that is if they agree on the subgroup.

The classical version of $Au=uA$ ends up as $a_{ij}=a_{\sigma(i)\sigma(j)}$… the group in question the classical $\text{Aut }\Gamma$. In that sense perhaps $Au=uA$ might be better given as $fA=Af$.

Easiest thing first, is it a *-ideal? Well, take the adjoint of $fA=Af\Rightarrow A^*f^*=f^*A^*$ and $A=A^*$ so $I$ is *closed. Suppose $f\in I$ and $g\in C(S_n^+)$… I cannot prove that this is an ideal! But time to move on.

### 3. The Existence of Two Cherries

In this section the authors will show that almost all trees have two cherries. Definition 3.4 says with clarity what a cherry is, here I use an image [credit: www-math.ucdenver.edu]:

(3,5,4) and (7,9,8) are cherries

#### Remark 3.2

If a graph admits a cherry $(u_1,u_2,v)$, the transposition $(u_1\quad u_2)$ is a non-trivial automorphism.

#### Theorem 3.3 (Erdos, Réyni)

Almost all trees contains at least one cherry in the sense that

$\displaystyle \lim_{n\rightarrow \infty}\mathbb{P}[C_n\geq 1]=1$,

where $C_n$ is #cherries in a (uniformly chosen) random tree on $n$ vertices.

#### Corollary 4.3

Almost all trees have symmetry.

The paper claims in fact that almost all trees have at least two cherries. This will allow some $S_4^+$ action to take place. This can be seen in this paper which is the next point of interest.