{'fraction_non_alphanumeric': 0.05684423465947404, 'fraction_numerical': 0.01935266351989211, 'mean_word_length': 3.5133901399878273, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 28, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Almost all trees have quantum symmetry

From the work of Erd\H{o}s and R\'{e}nyi from 1963 it is known that almost all graphs have no symmetry. In 2017, Lupini, Man\v{c}inska and Roberson proved a quantum counterpart: Almost all graphs have no quantum symmetry. Here, the notion of quantum symmetry is phrased in terms of Banica's definition of quantum automorphism groups of finite graphs from 2005, in the framework of Woronowicz's compact quantum groups. Now, Erd\H{o}s and R\'{e}nyi also proved a complementary result in 1963: Almost all trees do have symmetry. The crucial point is the almost sure existence of a cherry in a tree. But even more is true: We almost surely have two cherries in a tree - and we derive that almost all trees have quantum symmetry. We give an explicit proof of this quantum counterpart of Erd\H{o}s and R\'{e}nyi's result on trees.


Introduction and main results
Erdős and Rényi [ER63] proved that almost all graphs are asymmetric, in the following sense: When choosing a graph on n vertices uniformly at random, the probability that its automorphism group is trivial, tends to 1 as n tends to infinity. In contrast to this, they also showed that almost all trees are symmetric, i.e. the probability that the automorphism group of a random tree on n vertices is trivial, tends to 0 as n tends to infinity.
In recent years, the notion of a quantum automorphism group of a graph was introduced by Banica in [Ban05], modifying a preceding version by Bichon [Bic03]. It is a compact matrix quantum group in the sense of Woronowicz (see [Wor87]) enlarging the usual automorphism group of a graph and providing a subtler graph invariant. It is an interesting question, which graphs have a quantum automorphism group that is strictly larger than their classical automorphism group. In that case we say that the graph has quantum symmetry. In general, this question is very hard to answer. There are some sufficient criteria that one can check but usually, there is no 'easy' way to decide whether or not a graph has quantum symmetry. For results about specific graphs or specific classes of graphs see [BB07], [Sch18b], [SW18].
Recently, Lupini, Mančinska and Roberson proved a quantum version of the first Erdős Rényi Theorem mentioned in the beginning: Almost all graphs are quantum asymmetric, i.e. the quantum automorphism group of almost all graphs is trivial ( [LMR17]). A crucial ingredient in their proof is the so-called coherent algebra of a graph. They show that it provides a new sufficient criterion for a graph to be quantum asymmetric. We will give a few details of this in Section 4.
In this paper we give a proof of a quantum analogue of the second Erdős Rényi Theorem mentioned above, namely: Almost all trees have quantum symmetry. The crucial ingredient of Erdős and Rényi's proof is to show that almost all trees contain a so-called cherry (two vertices of degree one 'dangling' like a twin cherry on a common third vertex) -indeed, by flipping this twin cherry, we obtain a non-trivial automorphism. Interestingly, for proving the quantum analogue of this, it is enough to show that almost all trees contain at least two cherries from which we may derive the existence of two non-trivial automorphisms with disjoint supports. By applying a criterion of one of the authors of this article [Sch18a], this yields the result.
(iv) Almost all trees have quantum symmetry.
Let us note that the almost sure existence of two cherries in a tree is probably well-known to experts. Nevertheless, we give a direct proof of this fact in order to present a complete and concise proof of the quantum version of Erdős and Rényi's result on trees.

Preliminaries
In this section we give some mathematical background on compact (matrix) quantum groups, graphs and their (quantum) symmetries.
2.1. Graphs and Trees. A graph is a tuple Γ = (V, E) where V is a non-empty set of vertices and E ⊆ V × V is a set of edges (in particular, we don't allow a graph to have multiple edges between the same pair of vertices). It is called finite if V is finite, and undirected if we have (i, j) ∈ E whenever (j, i) ∈ E. An edge of the form (i, i) ∈ E is called a loop. If v ∈ V is a vertex, we define its degree to be the number of neighbours of v, i.e. the number of vertices u ∈ V such that (v, u) ∈ E.
We will only be concerned with finite undirected graphs without loops and without multiple edges. Furthermore, we will usually identify the vertex set V with the set {1, . . . , n} where n = #V .
A path of length k in a graph Γ = (V, E) is a k-tuple (e 1 , . . . , e k ) of edges e j = (u j , v j ) ∈ E such that v j = u j+1 for all j = 1, . . . k − 1. It is called a cycle if u 1 = v k . A graph is called connected if for every pair of vertices i, j ∈ V with i = j there is a path from i to j, i.e. u 1 = i and v k = j. A tree is a connected graph without cycles.
The adjacency matrix of a graph Γ = (V, E) is the matrix A = (a ij ) i,j∈V with entries Symmetries of Graphs. An automorphism of a graph Γ = (V, E) is a bijection σ : V → V that preserves adjacency and non-adjacency, i.e. (i, j) ∈ E if and only if (σ(i), σ(j)) ∈ E for all i, j ∈ V . The set of all automorphisms of Γ forms a group Aut(Γ) under composition and is called the automorphism group of Γ. It can be identified with a subgroup of the symmetric group S n (where n = #V ) which can in turn be embedded as permutation matrices in M n (C). The automorphism group then has a nice description in terms of the adjacency matrix A of Γ: We call a graph Γ symmetric, if there exists a non-trivial automorphism of Γ, and asymmetric otherwise.

Compact Matrix Quantum Groups.
Compact matrix quantum groups were first defined by Woronowicz [Wor87] in an attempt to generalize compact matrix groups. As a general reference for this we refer the reader to [Tim08], [NT13] or [Web17].
where B is a unital C * -algebra and u = (u ij ) n i,j=1 is a matrix with entries in B such that: (i) B is generated (as a C * -algebra) by the entries of u.
The matrix u and its transpose u t are invertible.
Example 2.2. Let G ⊆ GL n (C) be a compact matrix group and let (u ij ) n i,j=1 be the coordinate functions on G, i.e.
is the algebra of continuous complex-valued functions on G is a compact matrix quantum group. Moreover, all compact matrix quantum groups (B, u) with commutative C * -algebra B are of this form (see [Tim08, Proposition 6.1.11]). So under the identification of G with (C(G), u), compact matrix quantum groups generalize classical compact matrix groups.
Example 2.3. Another very important example of a compact matrix quantum group is the quantum symmetric group S + n defined by Wang in [Wan98]. It is given by the universal unital C * -algebra and it can be interpreted as a quantum analogue of the classical symmetric group S n . Indeed, we have a surjective * -homomorphism ϕ : C(S + n ) → C(S n ) sending generators to coordinate functions, thus we can think of S n as a quantum subgroup of S + n . The map ϕ is an isomorphism for n = 1, 2, 3 (so we have S + n = S n for n = 1, 2, 3) but for n ≥ 4, C(S + n ) is non-commutative and infinite-dimensional -we then have more quantum permutations than ordinary permutations.
2.4. Quantum symmetries of graphs. In 2003, Bichon [Bic03] gave a definition of a quantum automorphism group of a finite graph. It was modified by Banica [Ban05] in 2005. See also [SW18] for more on quantum symmetries of graphs.
Definition 2.4. [Ban05] Let Γ = (V, E) be a graph on n vertices without multiple edges and without loops and let A be its adjacency matrix. The quantum automorphism group QAut(Γ) of Γ is defined as the compact matrix quantum group with C * -algebra We have the inclusions Aut(Γ) ⊆ QAut(Γ) ⊆ S + n and we say that Γ has quantum symmetry, if the first inclusion is strict, i.e. if and only if C(QAut(Γ)) is noncommutative.

The existence of two cherries
In this section we show that almost all trees contain at least two cherries. This is probably well-known to experts, but in order to keep this article self-contained, we present a direct proof. We use this in the next section to prove our main result about the quantum symmetries of trees.
and v are pairwise distinct, (ii) u 1 and u 2 are adjacent to v, (iii) u 1 and u 2 have degree 1 and (iv) v has degree 3.
Remark 3.2. If a graph contains a cherry (u 1 , u 2 , v), then it admits the non-trivial automorphism that swaps u 1 and u 2 and fixes any other vertex. Hence the graph has symmetry.
Erdős and Rényi showed in [ER63] that almost all trees contain at least one cherry, implying that almost all trees are symmetric. So one can rephrase their result as follows. where C n is the number of cherries in a tree that is drawn uniformly at random from the set of all trees on n vertices.
Corollary 3.4. Almost all trees have symmetry.
We will now show that even lim n→∞ P[C n ≥ 2] = 1 holds in the above setting. The proof of this is only a slight modification of the proof of Theorem 3.3. Note however that we use a somewhat different notion of cherries than Erdős and Rényi. In their definition, the requirement (iv) from ours is missing. This changes the formulas in the subsequent proofs by a small degree in comparison with the original arguments in [ER63]. We begin by fixing some notation. For n ∈ N let T n be a tree on n vertices and denote these vertices by v 1 , . . . , v n . For every choice of indices i 1 , i 2 , j ∈ {1, . . . , n} we define is a cherry in T n 0 otherwise We equip the set of all trees on n vertices with the uniform probability measure, turning ε i 1 ,i 2 ,j into a random variable.
Note furthermore that by Cayley's formula, the number of labelled trees on n vertices is n n−2 . We will use this fact several times in the following proofs.
Proof. Since E[ε i 1 ,i 2 ,j ] = #{trees on n vertices with a cherry at (i 1 , i 2 , j)} #{trees on n vertices} we only have to calculate the numerator, as the denominator is n n−2 by Cayley's formula. Let T = (V, E) be a tree on n − 3 vertices labelled with {1, . . . , n} \ {i 1 , i 2 , j}. By attaching a cherry (v i 1 , v i 2 , v j ) at any vertex u ∈ V we can construct a tree on n vertices with a cherry at (i 1 , i 2 , j). On the other hand, any tree on n vertices with a cherry at (i 1 , i 2 , j) can be constructed in this way. Since T has n − 3 vertices, we have n − 3 possibilities for choosing u, thus there are (n − 3)(n − 3) n−5 = (n − 3) n−4 trees on n vertices with a cherry at (i 1 , i 2 , j), so the claim follows.
Lemma 3.6. Let i 1 , i 2 , j 1 , i 3 , i 4 , j 2 ∈ {1, . . . , n}. We have: In the case that all labels j 1 , i 1 , i 2 , j 2 , i 3 , i 4 are different from each other, we can attach cherries (v i 1 , v i 2 , v j 1 ) and (v i 3 , v i 4 , v j 2 ) at any two vertices u 1 and u 2 of Γ and thereby construct a tree on n vertices with two cherries at (i 1 , i 2 , j 1 ) and (i 3 , i 4 , j 2 ). On the other hand, every tree on n vertices with two cherries at (i 1 , i 2 , j 1 ) and (i 3 , i 4 , j 2 ) can be constructed in this way. Since T has n − 6 vertices, we have n − 6 possibilities for choosing u 1 and u 2 respectively. Thus there are (n − 6)(n − 6)(n − 6) n−8 = (n − 6) n−6 trees on n vertices with two cherries at (i 1 , i 2 , j 1 ) and (i 3 , i 4 , j 2 ).
In the case that j 1 , i 1 , i 2 are distinct, j 1 = j 2 and {i 1 , i 2 } = {i 3 , i 4 }, we can conclude as in the case of three labels (see Lemma 3.5) that the number of trees on n vertices with a cherry at (i 1 , i 2 , j 1 ) is (n − 3) n−4 .
In all other cases, there is no tree on n vertices with cherries at (i 1 , i 2 , j 1 ) and (i 3 , i 4 , j 2 ).
As in Theorem 3.3 we denote by C n (T n ) the number of cherries in the tree T n on n vertices. With the notation from above we can express this as Lemma 3.7. The expectation of C n is Proof. The number of 3-tuples (j, i 1 , i 2 ) ∈ {1, . . . , n} 3 such that all entries are distinct is n(n − 1)(n − 2). The further condition that i 2 < i 1 halves this number, so the expression in Equation (3.1) has n(n−1)(n−2) 2 summands. Hence, by Lemma 3.5: We now want to calculate the variance of C n . For this we need the second moment.
Lemma 3.8. The second moment of C n is Proof. Let T n be a random tree on n vertices. We first compute using Equation 3.1: To apply the formulas from Lemma 3.6 we split this sum into the two cases where j 1 , i 1 , i 2 , j 2 , i 3 , i 4 are all different and where either j 1 = j 2 and i 1 = i 3 , i 2 = i 4 or j 1 = j 2 and i 1 = i 4 , i 2 = i 3 and j 1 , i 1 , i 2 are different.

Asymptotics of (quantum) symmetries of graphs and trees
From Theorem 3.10 and the following criterion from [Sch18a], we may derive that almost all trees have quantum symmetry.
Let Γ = (V, E) be a graph and let σ : V → V be an automorphism of Γ. The set is called the support of σ. This also makes the importance of cherries clear. If a graph contains a cherry, it has a non-trivial automorphism of order two which swaps the two vertices of degree one in the cherry. So the graph has symmetry. If a graph has two cherries, it has two non-trivial disjoint automorphisms of order two. So by the above proposition, it has quantum symmetry. From this, we can conclude our main result, building on Theorem 3.10.
Theorem 4.2. Almost all trees have quantum symmetry.
For the convenience of the reader, let us briefly describe the arguments of [LMR17] for the non-existence of quantum symmetry for graphs.
A subset A ⊆ M n (C) is called a coherent algebra if it is a selfadjoint unital subalgebra of M n (C) both with respect to ordinary matrix multiplication as well as with respect to entrywise matrix multiplication (Schur product).
A class of examples of coherent algebras can be obtained from group actions: Let G be a group acting on a finite set X with n elements and let R 1 , . . . , R s be the orbits of the induced action of G on X × X (these are sometimes called orbitals). For each R i (i ∈ {1, . . . , s}) we define its characteristic matrix A (i) as Then the linear span of these matrices is a coherent algebra. One can also associate a coherent algebra to a graph Γ by considering the coherent algebra generated by its adjacency matrix. This is then called the coherent algebra of Γ and denoted by CA(Γ).
It is a well-known fact that the coherent algebra of a graph provides a sufficient criterion for a graph to be asymmetric: This is useful from a computational point of view since the coherent algebra of a graph can be computed in polynomial time using the two-dimensional Weisfeiler-Lehman algorithm (for details on this see [Für17]), whereas it is generally hard to compute the automorphism group of a graph or even to check whether or not it is trivial.
One of the key insights of Lupini, Mančinska and Roberson was that we can strengthen Proposition 4.3 to the following.