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 vertices *has no symmetry *goes to zero as .

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 ) 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 . 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 with iff there is an edge connected and . The adjacency matrix is symmetric.

### 2.2 Symmetries of Graphs

An *automorphism *of a graph is a permutation of that preserves adjacency and non-adjacency. The set of all such automorphisms, , is a group where the group law is composition. It is a subgroup of , and itself can be embedded as permutation matrices in . We then have

.

If , it is asymmetric. Otherwise it is or rather has symmetry.

### 2.3 Compact Matrix Quantum Groups

A *compact matrix quantum group *is a pair , where is a unital -algebra, and is such that:

- is generated by the ,
- There exists a morphism , such that
- and are invertible (Timmermann only asks that be invertible)

The classic example (indeed commutative examples all take this form) is a compact matrix group and the coordinates of .

#### Example 2.3

The algebra of continuous functions on the quantum permutation group is generated by projections such that the row sums and column sums of both equal .

The map , is a surjective morphism that is an isomorphism for , so that the sets have no quantum symmetries.

### 2.4 Quantum Symmetries of Graphs

#### Definition 2.4 (Banica after Bichon)

Let be a graph on vertices without multiple edges not loops, and let be its adjacency matrix. The *quantum automorphism group* is defined as the compact matrix group with -algebra:

For me, not the authors, this requires some work. Banica says that is a *Hopf ideal*.

A *Hopf ideal *is a closed *-ideal such that

.

Classically, the set of functions vanishing on a distinguished subgroup. The quotient map is , and if their difference is in , that is if they agree on the subgroup.

The classical version of ends up as … the group in question the classical . In that sense perhaps might be better given as .

Easiest thing first, is it a *-ideal? Well, take the adjoint of and so is *closed. Suppose and … 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 , the transposition is a non-trivial automorphism.

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

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

,

*where is #cherries in a (uniformly chosen) random tree on 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 action to take place. This can be seen in this paper which is the next point of interest.

## 1 comment

Comments feed for this article

May 16, 2020 at 10:59 am

A Sufficient Condition for Quantum Symmetry | J.P. McCarthy: Math Page[…] post follows on from this one. The purpose of posts in this category is for me to learn more about the research being done in […]