Quantum automorphisms of graphs
Final Report Abstract
The goal of our project Quantum automorphisms of graphs was to investigate sym- metries of finite graphs in the context of “quantum mathematics”. By a graph, we mean an object consisting in points (“vertices”) which may or may not be connected by lines (“edges”). Such a graph may have symmetries: It could be mapped to itself by a reflection or a rotation, for instance. More generally, the symmetries of a graph are described by its automorphism group, i.e. the set of all permutations of the vertices preserving the connections by edges. In quantum mathematics however, we have more possibilities for permuting vertices – we may “quantum permute” them. This way, we obtain more symmetries a priori: namely quantum symmetries. The quantum symmetries of a graph are described by a quantum group: its quantum automorphism group. These objects have been studied only quite recently and we know very little about them. In our project, we gained new insights into quantum symmetries of graphs. We de- termined for a quite large class whether it is really advantageous to be able to quantum permute the vertices of a given graph – or whether all of its symmetries are already given by its automorphism group. Moreover, we computed explicitely a number of quantum automorphism groups. In this context, we also developed various computer based tools helping to detect the existence of honest quantum symmetries of a given graph. Moreover, we obtained probabilistic statements about trees (forming a subclass of graphs): Choosing randomly a graph which is also a tree, it will almost surely have quantum symmetries. We were involved in some surprising, new developments linking the concept of quan- tum symmetries of graphs with quantum information theory. They reveal that methods from quantum mathematics finally yield insight also for “classical” mathematics. It be- comes more and more apparent that quantum symmetries are a strong and far reaching phenomenon. Since all of our investigations are in the realm of fundamental research, there are no immediate applications in industry. However, we expect that quantum mathematics as a whole eventually will lead – with some delay – to groundbreaking results also in everyday life. With our project, we contributed to a first, fundamental understanding of the underlying structures.
Publications
- Quantum symmetries of graph C*-algebras. Canadian Mathematical Bulletin, Vol. 61(4), pages 848–864, 2018
Schmidt, Simon; Weber, Moritz
(See online at https://doi.org/10.4153/cmb-2017-075-4) - The Petersen graph has no quantum symmetry. Bulletin of the London Mathematical Society, Vol. 50, Issue 3, pages 395–400, June 2018
Schmidt, Simon
(See online at https://doi.org/10.1112/blms.12154) - Existence of quantum symmetries for graphs on up to seven vertices: a computer based approach. 15 pages + appendix (2019)
Eder, Christian; Levandovskyy, Viktor; Schanz, Julien; Schmidt, Simon; Steenpass, Andreas; Weber, Moritz
(See online at https://doi.org/10.48550/arXiv.1906.12097) - Uniformly vertex-transitive graphs. 17 pages (2019)
Schmidt, Simon; Vogeli, Chase; Weber, Moritz
(See online at https://doi.org/10.48550/arXiv.1912.00060) - Almost all trees have quantum symmetry. Archiv der Mathematik, Vol. 115, 367–378, 2020
Junk, Luca; Schmidt, Simon; Weber, Moritz
(See online at https://doi.org/10.1007/s00013-020-01476-x) - On the quantum symmetry of distance-transitive graphs. Advances in Mathematics, Vol. 368, 107150, 15 July 2020
Schmidt, Simon
(See online at https://doi.org/10.1016/j.aim.2020.107150) - Quantum automorphisms of folded cube graphs. Annales de l’Institut Fourier, Vol. 70. no. 3, 949–970, 2020
Schmidt, Simon
(See online at https://doi.org/10.5802/aif.3328) - Quantum symmetry vs nonlocal symmetry. 44 pages (2020)
Roberson, David; Schmidt, Simon
(See online at https://doi.org/10.48550/arXiv.2012.13328) - Sinkhorn algorithm for quantum permutation groups. To appear in Experimental Mathematics, 2020.16 pages
Nechita, Ion; Schmidt, Simon; Weber, Moritz
(See online at https://doi.org/10.48550/arXiv.1911.04912)
