Growth in finite groups and the Graph Isomorphism Problem
von Daniele Dona
Datum der mündl. Prüfung:2020-07-17
Erschienen:2020-08-19
Betreuer:Prof. Dr. Harald Andrés Helfgott
Gutachter:Prof. Dr. Harald Andrés Helfgott
Gutachter:Prof. Dr. Laurent Bartholdi
Dateien
Name:Thesis revised.pdf
Size:948.Kb
Format:PDF
Zusammenfassung
Englisch
The present thesis embraces two major areas of mathematics, namely group theory (especially growth in finite groups) and graph theory (especially the graph isomorphism problem). Several results are presented coming from both areas: on one side, we show that the dependence of the diameter of a product of finite simple groups on the diameter of its factors is linear, and we extend the analysis of sets of small growth in the affine group over a prime field to the same group over general finite fields; on the other, we show a dependence of the number of iterations of the Weisfeiler-Leman algorithm over Schreier and Cayley graphs on the diameter of such graphs. Finally, analyzing Babai's algorithm for solving the graph isomorphism problem, we pave a possible way towards a proof of a diameter bound for the alternating group that does not rely on the classification of finite simple groups.
Keywords: Growth in groups; Graph Isomorphism Problem; Diameter; CFSG; Weisfeiler-Leman; Affine group; Product of simple groups; Schreier graphs; Alternating group