Quantum symmetries of combinatorial structures: A computer assisted approach

Abstract

In this thesis, we study the quantum symmetries of various combinatorial objects. More precisely, we investigate the quantum automorphism groups of vertex- transitive graphs, which were first defined by Banica and Bichon in [4], [13], and introduce the new notions of quantum switching isomorphisms of signed graphs and quantum automorphism groups of matroids. The results include a complete determination of the existence of quantum symmetries of all vertex-transitive graphs on 12 vertices, extending work done in [6], [22], [23], and the computation of the quantum automorphism groups of two of these graphs aided by a Gröbner basis computation. Inspired by the graph isomorphism game introduced in [2], we moreover constructed a switching isomorphism game for signed graphs. Analogously to the study of the graph isomorphism game in [51], we find that there is a strong connection between the perfect quantum strategies for the switching isomorphism game and the hyperoctahedral quantum group. However, we also find that for connected signed graphs, any true quantum switching isomorphism always implies the existence of a true quantum isomorphism of the underlying graphs. Lastly, we define several quantum automorphism groups for matroids. It turns out that unlike the classical automorphism groups of matroids, the quantum automorphism groups depend on the axiom system chosen for the matroid. We then study the quantum automorphism groups of several matroids, using amongst others Gröbner basis computations. This work is based in parts on the research articles [26], [73] of which the author of the thesis was the author and a coauthor respectively.

In dieser Arbeit untersuchen wir die Quantensymmetrien verschiedener kombinatorischer Objekte. Um genauer zu sein, befassen wir uns mit den Quantenautomorphismengruppen von vertextransitiven Graphen, die zuerst von Banica und Bichon in [4], [13] definiert wurden, und führen die neuen Begriffe der Quantenswitchingisomorphie von signierten Graphen und der Quantenautomorphismengruppen von Matroiden ein. Unter den Ergebnissen ist eine vollständige Bestimmung der Existenz von Quantensymmetrien von allen vertextransitiven Graphen auf 12 Punkten. Dies erweitert die Arbeit aus [6], [22], [23]. Weiterhin berechnen wir die Quantenautomorphismen- gruppen von zwei dieser Graphen, wobei teilweise auf Gröbnerbasisberechnungen zurückgegriffen wird. Außerdem konstruieren wir ein Switching-Isomorphie-Spiel für signierte Graphen nach dem Vorbild des Graph-Isomorphie-Spiels aus [2]. Analog zur Analyse des Graph-Isomorphie-Spiels in [51] können wir zeigen, dass es eine starke Verbindung zwischen perfekten Quantenstrategien für das Switching-Isomorphie-Spiel und der hyperoktaedrische Quantengruppe. Wir können allerdings auch zeigen, dass für zusammenhängende signierte Graphen jeder wahre Quantenswitchingisomorphismus schon die Existenz eines wahren Quantenswitchingisomorphismus der zugrunde liegenden Graphen impliziert. Schließlich definieren wir verschiedene Quantenautomorphismengruppen für Matroide. Es stellt sich heraus, dass – anders als die klassische Automorphismengruppen von Matroiden – die Quantenautomorphismengruppen von dem Axiomsystem abhängt, welches man wählt um den Matroid zu beschreiben. Wir untersuchen die Quantenautomorphismengruppen von verschiedenen Matroiden, unter anderem mithilfe von Gröbnerbasisberechnungen. Diese Arbeit basiert teilweise auf den Forschungsartikeln [26], [73], welche der Autor der Dissertation verfasst bzw. mitverfasst hat.