Quantum automorphism groups of finite graphs

Abstract

The present work contributes to the theory of quantum permutation groups. More specifically, we develop techniques for computing quantum automorphism groups of finite graphs and apply those to several examples. Amongst the results, we give a criterion on when a graph has quantum symmetry. By definition, a graph has quantum symmetry if its quantum automorphism group does not coincide with its classical automorphism group. We show that this is the case if the classical automorphism group contains a pair of disjoint automorphisms. Furthermore, we prove that several families of distance-transitive graphs do not have quantum symmetry. This includes the odd graphs, the Hamming graphs H(n, 3), the Johnson graphs J(n,2), the Kneser graphs K(n,2) and all cubic distance-transitive graphs of order ≥ 10. In particular, this implies that the Petersen graph does not have quantum symmetry, answering a question asked by Banica and Bichon in 2007. Moreover, we show that the Clebsch graph does have quantum symmetry and prove that its quantum automorphism group is equal to SO_5^{−1} answering a question asked by Banica, Bichon and Collins. More generally, for odd n, the quantum automorphism group of the folded n-cube graph is SO_n^{-1} . With one graph missing, we can now decide whether or not a distance-regular graph of order ≤ 20 does have quantum symmetry. We present a table including those results. As a byproduct, we obtain a pair of distance-regular graphs with the same intersection array, where one of them does have quantum symmetry and the other one does not. Additionally, we discuss connections of quantum automorphism groups of finite graphs to planar algebras associated to group actions and quantum isomorphisms of graphs. Using those connections, we give two examples of graphs with quantum symmetry, whose automorphism groups do not contain any pair of disjoint automorphisms. Those are the Higman-Sims graph and a graph obtained from a linear binary constraint system. This work contains the results of the three research articles [48], [49] and [50] by the author. The other articles ([25], [35], [41], [51], [52]) by the author are mentioned in the margin.

Die vorliegende Arbeit trägt zur Theorie der Quantenpermutationsgruppen bei. Genauer gesagt entwickeln wir Techniken zur Berechnung von Quantenautomorphismengruppen endlicher Graphen und wenden diese auf mehrere Beispiele an. Unter anderem geben wir ein Kriterium an, wann ein Graph Quantensymmetrie hat. Per Definition hat ein Graph Quantensymmetrie, wenn seine Quantenautomorphismengruppe nicht mit der klassischen Automorphismengruppe übereinstimmt. Wir zeigen dass dies der Fall ist, wenn die klassische Automorphismengruppe ein Paar von disjunkten Automorphismen enthält. Außerdem beweisen wir, dass mehrere Familien von distanz-transitiven Graphen keine Quantensymmetrie haben. Dazu gehören die Odd-Graphen, die Hamming-Graphen H(n,3), die Johnson-Graphen J (n, 2), die Kneser-Graphen K (n, 2) und alle kubischen distanz-transitiven Graphen der Ordnung ≥ 10. Dies zeigt insbesondere, dass der Petersen-Graph keine Quantensymmetrie aufweist, was eine Frage von Banica und Bichon aus dem Jahr 2007 beantwortet. Darüber hinaus zeigen wir, dass der Clebsch-Graph Quantensymmetrie besitzt und beweisen, dass seine Quantenautomorphismengruppe gleich SO_5^{-1} ist, was eine Frage von Banica, Bichon und Collins beantwortet. Allgemeiner ist die Quantenautomorphismengruppe des gefalteten n-Würfel-Graphen SO_n^{−1}, für ungerade n. Mit einer Ausnahme können wir jetzt entscheiden, ob ein distanz-regulärer Graph der Ordnung ≤ 20 Quantensymmetrie hat oder nicht. Wir präsentieren eine Tabelle mit diesen Ergebnissen. Als Nebenprodukt erhalten wir ein Paar distanz-regulärer Graphen mit demselben Intersection array, wobei einer von ihnen Quantensymmetrie aufweist und der andere nicht. Zusätzlich diskutieren wir Zusammenhänge von Quantenautomorphismengruppen endlicher Graphen mit planaren Algebren, die von Gruppenwirkungen kommen, und Quantenisomorphismen von Graphen. Mit Hilfe dieser Zusammenhänge geben wir zwei Beispiele für Graphen mit Quantensymmetrie an, deren Automorphismengruppe jeweils kein Paar disjunkter Automorphismen enthält. Es handelt sich um den Higman-Sims-Graphen und einen Graphen, der aus einem linearen binären Gleichungssystem konstruiert wurde. Diese Arbeit enthält die Ergebnisse der drei Forschungsartikel [48], [49] und [50] des Autors. Die anderen Arbeiten ([25], [35], [41], [51], [52]) des Autors finden am Rande Erwähnung.