# Growth in finite groups and the Graph Isomorphism Problem

 dc.contributor.advisor Helfgott, Harald Andrés Prof. Dr. dc.contributor.author Dona, Daniele dc.date.accessioned 2020-08-19T12:01:33Z dc.date.available 2020-08-19T12:01:33Z dc.date.issued 2020-08-19 dc.identifier.uri http://hdl.handle.net/21.11130/00-1735-0000-0005-145F-B dc.identifier.uri http://dx.doi.org/10.53846/goediss-8163 dc.language.iso eng de dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/4.0/ dc.subject.ddc 510 de dc.title Growth in finite groups and the Graph Isomorphism Problem de dc.type doctoralThesis de dc.contributor.referee Helfgott, Harald Andrés Prof. Dr. dc.date.examination 2020-07-17 dc.description.abstracteng 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. de dc.contributor.coReferee Bartholdi, Laurent Prof. Dr. dc.subject.eng Growth in groups de dc.subject.eng Graph Isomorphism Problem de dc.subject.eng Diameter de dc.subject.eng CFSG de dc.subject.eng Weisfeiler-Leman de dc.subject.eng Affine group de dc.subject.eng Product of simple groups de dc.subject.eng Schreier graphs de dc.subject.eng Alternating group de dc.identifier.urn urn:nbn:de:gbv:7-21.11130/00-1735-0000-0005-145F-B-6 dc.affiliation.institute Fakultät für Mathematik und Informatik de dc.subject.gokfull Mathematik (PPN61756535X) de dc.identifier.ppn 1727500040
﻿