Classifications at the intersection of group and graph theory

Motivated by open problems posed by Cameron and Cherlin, this thesis provides new illuminating classifications at the intersection of group and graph theory. We achieve these classifications by exploring the relationship between graphs and groups in both directions: one by investigating a specific graph that can be defined on a group, and the other by investigating the structure of the automorphism groups of certain graphs.

In more detail, on the one hand, we employ a combination of graph-theoretic techniques and group properties to obtain classifications of certain finite groups. The work focuses on particular forbidden induced subgraphs of the power graph. The power graph encodes information on powers of elements within a group. We show that forbidding induced paths of length four in the power graph reveals strong restrictions on centralizers, whereas forbidding induced cycles in the power graph forces certain relations between commuting elements in a group. Altogether, we provide classifications of the finite non-nilpotent power-cograph groups and finite simple power-chordal groups. These classifications answer two questions of Cameron.

Moreover, on the other hand, we use group-theoretic and combinatorial techniques to classify certain finite ultrahomogeneous colored binary relational structures. A relational structure is ultrahomogeneous if every isomorphism of finite induced substructures extends to an automorphism of the whole structure. We first classify the finite ultrahomogeneous binary relational structures with one asymmetric binary relation and arbitrarily many unary relations, that is, we classify the finite vertex-colored oriented ultrahomogeneous graphs. The classification comprises several general methods with which directed graphs can be combined or extended to create new ultrahomogeneous graphs. Our main technique is a technical tool that characterizes precisely under which conditions two binary relational structures with disjoint unary relations can be combined to form a larger ultrahomogeneous structure.

Furthermore, we develop a practical algorithm to enumerate all finite ultrahomogeneous edge-colored graphs up to a specified order. As input, the algorithm can take either a list of all coherent configurations or all transitive permutation groups. Efficiency is achieved by pruning wreath products quickly. We determine the number of objects up to isomorphism for orders up to 34. These two results give a partial answer to a general question of Cherlin that asks for a classification of colored ultrahomogeneous graphs.

Angeregt durch offene Probleme, die von Cameron und Cherlin gestellt wurden, leuchtet diese Arbeit das Zusammenspiel von Gruppen- und Graphentheorie durch neue Klassifikationen weiter aus. Wir erreichen diese Klassifikationen, indem wir die Beziehung zwischen Graphen und Gruppen aus zwei verschiedenen Blickwinkeln erforschen: Durch die Untersuchung von Graphen, die durch eine Gruppe bestimmt werden, und durch die Untersuchung von Symmetriegruppen, die durch einen Graphen bestimmt werden.

Im Einzelnen setzen wir eine Kombination aus graphentheoretischen Techniken und Gruppeneigenschaften ein, um Klassifikationen bestimmter endlicher Gruppen zu erhalten. Diese Arbeit konzentriert sich auf bestimmte verbotene Subgraphen des Potenzgraphen. Der Potenzgraph kodiert Informationen über Potenzen von Elementen innerhalb einer Gruppe. Wir zeigen, dass das Verbot von induzierten Pfaden der Länge vier im Potenzgraphen starke Beschränkungen für Zentralisatoren impliziert, während das Verbot von induzierten Zyklen im Potenzgraphen bestimmte Beziehungen zwischen kommutierenden Elementen in einer Gruppe erzwingt. Insgesamt liefern wir Klassifikationen der endlichen nicht-nilpotenten Potenzcographengruppen und endlichen einfachen Potenzchordalgraphengruppen. Diese Klassifikationen beantworten zwei Fragen von Cameron.

Darüber hinaus verwenden wir gruppentheoretische und kombinatorische Techniken zur Klassifikation bestimmter endlicher ultrahomogener gefärbter binärer relationaler Strukturen. Eine relationale Struktur ist ultrahomogen, falls jeder Isomorphismus von endlichen induzierten Substrukturen sich zu einem Automorphismus der Gesamtstruktur fortsetzen lässt. Wir klassifizieren zunächst die endlichen ultrahomogenen binären relationalen Strukturen mit einer asymmetrischen binären Relation und beliebig vielen unären Relationen, das heißt, wir klassifizieren die endlichen ultrahomogenen knotengefärbten orientierten Graphen. Für die Klassifikation entwickeln wir mehrere neue allgemeine Methoden, mit denen Graphen kombiniert oder erweitert werden können, um neue ultrahomogene Graphen zu erzeugen. Unsere wichtigste Methode dabei ist ein technisches Werkzeug, das genau charakterisiert, unter welchen Bedingungen zwei binäre relationale Strukturen mit disjunkten unären Relationen zu einer größeren ultrahomogenen Struktur kombiniert werden können.

Zudem entwickeln wir einen praktischen Algorithmus zur Aufzählung aller endlichen ultrahomogenen binären relationalen Strukturen bis zu einer bestimmten Ordnung. In der Sprache der Graphen ausgedrückt: Wir bestimmen alle ultrahomogenen kantengefärbten Graphen bis zu einer bestimmten Ordnung. Als Eingabe erhält der Algorithmus entweder eine Liste aller kohärenten Konfigurationen oder aller transitiven Permutationsgruppen bis zur vorgegebenen Ordnung. Effizienz erreichen wir durch schnelles Pruning von Kranzprodukten. Wir bestimmen die Anzahl der Objekte bis auf Isomorphie bis Ordnung 34. Diese zwei Ergebnisse geben eine Teilantwort auf die Frage von Cherlin nach einer Klassifikation von gefärbten ultrahomogenen Graphen.