Structure theory and algorithms for highly regular colored graphs

Highly regular finite graphs are mesmerizing combinatorial objects. Their core characteristics exhibit how the structure of local subgraphs relates to the global structure of the whole graph. They have applications in various mathematical fields such as statistics, coding theory, and the general study of symmetries.

We call a graph highly regular if it is k-ultrahomogeneous or ℓ-tuple regular for suitable k, ℓ ∈ N: a graph is k-ultrahomogeneous if every isomorphism between two induced subgraphs of order at most k extends to an automorphism of the entire graph. Further, it is ultrahomogeneous if it is simultaneously k-ultrahomogeneous for all k ∈ N. In contrast, a graph is ℓ-tuple regular if the number of common neighbors of a vertex set S of order at most ℓ only depends on the isomorphism type of the subgraph induced by S. These graph properties have been studied extensively in the past. Especially, 1-ultrahomogeneity and 2-tuple regularity are better known as vertex-transitivity and strong regularity, respectively.

The focus of this thesis lies in the investigation of highly regular colored graphs. These naturally appear in the context of symmetries and graph isomorphism algorithms. For example, the well-studied Weisfeiler-Leman algorithms form a family of incomplete approaches to the graph isomorphism problem. They store combinatorial information on the local structure of a graph by coloring it. In particular, the ℓ-tuple regular colored graphs are closely related to the ℓ-dimensional Weisfeiler-Leman algorithm. The amount of information needed to distinguish a graph from non-isomorphic ones is measured by the Weisfeiler-Leman dimension. Altogether, colored graphs are a natural choice to examine for high regularity.

In this thesis, we classify the ℓ-tuple regular vertex-colored undirected finite graphs and the k-ultrahomogeneous vertex-colored undirected finite graphs for ℓ ≥ 5 and k ≥ 4. In particular, this includes the classification of ultrahomogeneous vertex-colored undirected finite graphs. Beyond that, we exhaustively enumerate all k-ultrahomogeneous and ℓ-tuple regular arc-colored directed finite graphs of order at most 34. In recent years, the Weisfeiler-Leman dimension has become a standard measure of descriptive complexity of a graph. We establish a lower bound of 0.0105027 · n − o(n) and an upper bound of 0.15 · n + o(n) for the Weisfeiler-Leman dimension of n-vertex graphs. We reduce the claim for the upper bound to 2-tuple regular colored graphs. Given the complexity of their structure, we develop new techniques to facilitate their analysis. This includes conditions under which a vertex color class can be restored, up to isomorphism, if it is removed. Within our proof, we also derive an upper bound of 0.05 · n + o(n) on the Weisfeiler-Leman dimension of colored graphs whose color classes all have size at most 7.

Hochreguläre endliche Graphen sind faszinierende kombinatorische Objekte. Ihre übergeordnete Struktur wird maßgeblich durch induzierte Subgraphen beeinflusst und beschrieben. Sie finden Anwendung in verschiedenen mathematischen Gebieten wie zum Beispiel Statistik, Kodierungstheorie oder bei der Analyse von Symmetrien.

Wir bezeichnen einen Graphen als hochregulär, falls er k-ultrahomogen oder ℓ-tupelregulär für geeignete k, ℓ ∈ N ist. Ein Graph heißt k-ultrahomogen, falls jeder Isomorphismus zwischen zwei induzierten Subgraphen mit höchstens k Knoten sich zu einem Automorphismus des Graphen fortsetzen lässt. Weiterhin wird ein Graph als ultrahomogen bezeichnet, wenn er für alle k ∈ N gleichzeitig k-ultrahomogen ist. Im Gegensatz dazu hängt in einem ℓ-tupelregulären Graphen die Anzahl gemeinsamer Nachbarn einer Knotenmenge M nur von dem Isomorphietypen des von M induzierten Subgraphen ab. Diese Grapheigenschaften wurden in zahlreichen Publikationen untersucht, wobei die 2-tupelregulären und die 1-ultrahomogenen Graphen besser bekannt sind als stark reguläre beziehungsweise transitive Graphen.

Diese Arbeit beschäftigt sich mit hochregulären gefärbten Graphen. Sie treten auf natürliche Weise im Kontext von Symmetrien und Algorithmen für Graphenisomorphie auf. Beispielsweise bilden die Weisfeiler-Leman Algorithmen eine Familie von Algorithmen, die sich mit dem Graphenisomorphieproblem beschäftigen. Sie nutzen Farben, um kombinatorische Informationen über Substrukturen eines Graphen zu sammeln. Besonders die ℓ-tupelregulären gefärbten Graphen stehen in enger Beziehung zum ℓ-dimensionalen Weisfeiler-Leman Algorithmus. Die Weisfeiler-Leman Dimension misst die Menge der Informationen, die erforderlich ist, um den Graphen von einem anderen nicht-isomorphen Graphen zu unterscheiden. Insgesamt sind gefärbte Graphen interessante Objekte, um sie auf hohe Regularität hin zu untersuchen.

In dieser Arbeit klassifizieren wir die k-ultrahomogenen knotengefärbten ungerichteten endlichen Graphen und die ℓ-tupelregulären knotengefärbten ungerichteten endlichen Graphen für alle k ≥ 4 und ℓ ≥ 5. Dies umfasst auch die Klassifikation der ultrahomogenen knotengefärbten ungerichteten endlichen Graphen. Weiterhin zählen wir alle k-ultrahomogenen und ℓ-tupelregulären kantengefärbten gerichteten endlichen Graphen mit höchstens 34 Knoten auf.

Heutzutage gilt die Weisfeiler-Leman Dimension als Standardmaß der strukturellen Komplexität eines Graphen. Wir beweisen eine neue untere Schranke von 0,0105027 · n − o(n) und eine obere Schranke von 0,15 · n + o(n) für die Weisfeiler-Leman Dimension eines Graphen der Ordnung n. Die Aussage über die obere Schranke führen wir auf 2-tupelreguläre gefärbte Graphen zurück. Da ihre Struktur schwer zu beschreiben ist, entwickeln wir neue Techniken zu ihrer Analyse. Zu diesen gehören auch Bedingungen, unter welchen eine Knotenfarbklasse bis auf Isomorphie wiederhergestellt werden kann, nachdem sie zuvor entfernt wurde. Als Zwischenschritt des Beweises etablieren wir eine obere Schranke von 0,05 · n + o(n) für die Weisfeiler-Leman Dimension von gefärbten Graphen, deren Ordnung n ist und die nur Farbklassen der Größe 7 oder kleiner enthalten.