Growth in finite groups and the Graph Isomorphism Problem

by Daniele Dona
Doctoral thesis
Date of Examination:2020-07-17
Date of issue:2020-08-19
Advisor:Prof. Dr. Harald Andrés Helfgott
Referee:Prof. Dr. Harald Andrés Helfgott
Referee:Prof. Dr. Laurent Bartholdi
Persistent Address: http://dx.doi.org/10.53846/goediss-8163

 

 

Files in this item

Name:Thesis revised.pdf
Size:948.Kb
Format:PDF

The following license files are associated with this item:

Abstract

English

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
 
Statistik