Almost all trees have quantum symmetry
- PDF / 355,022 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 79 Downloads / 213 Views
Archiv der Mathematik
Almost all trees have quantum symmetry Luca Junk , Simon Schmidt, and Moritz Weber
Abstract. From the work of Erd˝ os and R´enyi from 1963, it is known that almost all graphs have no symmetry. In 2017, Lupini, Manˇcinska, 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˝ os and R´enyi 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˝ os and R´enyi’s result on trees. Mathematics Subject Classification. Primary: 46LXX; Secondary: 20B25, 05CXX. Keywords. Compact quantum groups, Quantum automorphism groups of graphs, Quantum symmetries of graphs.
1. Introduction and main results. Erd˝ os and R´enyi [5] 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 [1], modifying a preceding version by Bichon [3]. Simon Schmidt and Moritz Weber were supported by the DFG project Quantenautomorphismen von Graphen. Moritz Weber was supported by the SFB-TRR 195. This work was part of the Luca Junk Bachelor’s thesis written under the supervision of the other two authors.
L. Junk et al.
Arch. Math.
It is a compact matrix quantum group in the sense of Woronowicz (see [15]) 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 [2], [9], [11]. Recently, Lupini, Manˇcinska, and Roberson proved a quantum version of the first Erd˝ os R´enyi theorem mentioned in the beginning: Almost all graphs are quantum asymmetric, i.e. the quantum automorphism group of almost all graphs is trivial ([7]). 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 asym
Data Loading...
