Distinguishing and witnessing dense structures in graphs and abstract separation systems

Abstract

This dissertation is concerned with the theory of tangles in abstract separation systems, which is part of the general field of structural graph theory. Tangles are a novel, universal tool to describe clusters in various structures, such as graphs, matroids or arbitrary data sets. They do so in an indirect way, built on the concept of separations of the given structure. They describe a cluster by deciding, for every possible way to `sensibly' divide the structure into two parts, on which of the two sides the cluster is suspected to be located. I.e., they orient the separation given by the two parts towards the side containing the cluster. Certain consistency axioms on these orientations of separations ensure that the tangle indeed needs to point towards a cohesive region of the structure at hand.

The broad application of tangles to a variety of contexts was made possible by the general framework of abstract separation systems, in which tangles can be formulated in an abstract way. As such, results about tangles in this abstract framework can then directly be applied in the various contexts mentioned above. Consequently, also most parts of this thesis are formulated in the context of these abstract separation systems.

The results of this thesis are spread across three chapters. First, in Chapter 3, we are dealing with the task of finding concrete witnesses for the existence of a cluster described by a tangle. We provide a partial solution to a question by Diestel by showing that, given a tangle of a graph, we can always find a weight function on the vertices of the graph so that the given tangle chooses, for every separation of the graph, the side containing a higher total weight. We also analyse variations and generalizations of this question and consider the general question of how to witness the existence of a tangle via another structure in contexts other than graphs.

Moreover, we also provide a quantitative characterization of another type of highly connected structures in graphs, called agile sets, via specific minors.

In Chapter 4 we present results concerning the question of how to split up a structure according to their tangles. One of the two types of classic results about tangles, the tree-of-tangles theorem, states that, under certain conditions, a structure, such as a graph, can be split up in a tree-like way according to its tangles. We improve the two previously most general forms of this tree-of-tangles theorem significantly in multiple ways.

For example, we identify the key property needed for the various tree-of-tangle theorems to hold and thereby provide two simple, elementary lemmas which allow to obtain the most relevant previously known tree-of-tangles theorems as corollaries. Moreover, the requirements of these lemmas are easy to check, and they allow us to obtain tree-of-tangles theorems for contexts where such theorems were previously not known. Additionally, we show that these lemmas even allow applications in contexts not covered by the framework of abstract separation systems, such as directed graphs, by also deducing a state-of-the-art tree-of-tangles theorem for tangles in directed graphs from one of the two lemmas.

We also show that trees of tangles can be constructed canonical, that is invariant under isomorphisms, in a more general context than previously known. While previously, a canonical tree-of-tangles theorem was only proven in the context of a submodular universe of separations, we prove such a theorem for submodular separation systems, a setup in which previously only the existence of a non-canonical tree-of-tangles theorem was known.

We additionally show the existence of tree-of-tangles theorems in infinite contexts, by providing, in the infinite context, a lemma analogue to the two simple lemmas mentioned above. This lemma can, as a side effect, be applied to the separators of an infinite graph instead of the separations. We show that the application to these separators gives us a canonical tree-like structure dividing up the graph according to its tangles which is of particular interest since both, a previously known non-canonical tree-of-tangles theorem for infinite graphs, and a previously known canonical theorem, which provides a structure called a tree of tree-decompositions, can be deduced from our theorem.

Moreover, our lemma about trees of tangles in infinite structures can also be used to obtain a tree-of-tangles theorem for the edge-blocks of a graph: the maximal subgraphs of an infinite graph which can not be separated by the deletion of some fixed number of edges.

We close Chapter 4 with showing that the other type of classic result from tangle theory, the tangle-tree-duality theorem, can in fact be used to prove a tree-of-tangles theorem. Thus, these two different classic types of theorems from tangle theory are not as independent as previously thought, since one of the two types of results can be used to obtain a result of the other type.

Finally, in Chapter 5, we investigate abstract separation systems as an object of its own interest. We not only provide examples of such systems which show that some of the previously defined notions on these systems, namely the notions of a submodular universe of separations and of a submodular separation systems mentioned above, indeed describe different objects, we also analyse their difference. This on the one hand leads to a decomposition theorem for submodular separation systems inside distributive universes, on the other hand we end up with a general question about certain families of finite sets, which we call woven. Our unravelling problem, which we state at the end of Chapter 5, is a simple to state problem about these woven sets. We analyse this problem, solve it in certain cases and provide solutions for some variations of that problem.

Diese Dissertation beschäftigt sich mit der Theorie von Tangles in abstrakten Teilungssystemen, einem Teilgebiet der strukturellen Graphentheorie. Tangles sind ein neues, universelles Werkzeug, um Cluster in verschiedenen Strukturen wie Graphen, Matroiden oder beliebigen Datenmengen zu beschreiben. Sie ermöglichen es, ein Cluster indirekt mit Hilfe des Konzepts der Teilungen einer Struktur zu beschreiben, indem ein Tangle für jede mögliche Art und Weise, die Struktur "sinnvoll" in zwei Teile zu zerteilen, entscheidet, in welchem der beiden Teile das Cluster vermutet wird. Mit anderen Worten, das Tangle "orientiert" die Teilung, die durch die zwei Teile gegeben ist, in Richtung der Seite, die das Cluster enthält. Bestimmte Konsistenz-Bedingungen an diese Orientierungen von Teilungen stellen sicher, dass das Tangle auch wirklich auf eine hoch-zusammenhängende Region der Struktur zeigt.

Das Konzept von Tangles kann abstrakt im Framework der abstrakten Teilungssysteme formuliert werden. Dies ermöglicht eine vereinheitlichte Anwendung von Tangles in einer Reihe von verschiedenen Bereichen, wie zum Beispiel den oben erwähnten. Dadurch können Erkenntnisse über Tangles in diesem abstrakten Framework direkt auf die verschiedenen Kontexte angewendet werden. Aus diesem Grund sind auch die meisten Teile dieser Arbeit im Kontext dieser abstrakten Teilungssysteme formuliert.

Die Ergebnisse dieser Arbeit werden in drei Kapiteln dargestellt. Zunächst beschäftigen wir uns in Kapitel 3 mit der Suche nach konkreten Strukturen, die die Existenz eines indirekt durch Tangles beschriebene Clusters garantieren. So präsentieren wir eine Teillösung zu einer Frage von Diestel, indem wir zeigen, dass man für ein gegebenes Tangle in einem Graphen immer eine Gewichtsfunktion auf den Ecken des Graphens finden kann, sodass das gegebene Tangle für jede Teilung des Graphens die Seite auswählt, die in Summe ein höheres Gewicht enthält. Zudem beschäftigen wir uns mit Variationen und Verallgemeinerungen dieser Frage, nämlich ganz generell damit, wie die Existenz eines Tangles auch außerhalb des spezifischen Kontextes von Graphen durch andere Strukturen bezeugt werden kann.

Außerdem charakterisieren wir über spezifische Minoren quantitativ die Existenz eines anderen Typen von hoch zusammenhängenden Strukturen in Graphen, sogenannten agilen Mengen.

In Kapitel 4 präsentieren wir mögliche Antworten auf die Frage, wie man eine gegeben Struktur entlang ihrer Tangles aufsplitten kann. Einer der zwei klassischen Sätze über Tangles ist der sogenannte "Tree-of-Tangles-Satz", der besagt, dass man unter gewissen Bedingungen eine Struktur wie zum Beispiel einen Graphen baumartig entsprechend der Tangles zerlegen kann. Wir beweisen stärkere und allgemeinere Versionen der beiden bisher allgemeinsten Formen dieser Tree-of-Tangles-Sätze.

So identifizieren wir zum Beispiel eine zentrale Eingenschaft, die für die Gültigkeit solcher Tree-of-Tangles-Sätze notwendig ist, und verwenden diese, um zwei einfache, elementare Lemmata zu beweisen, die es ermöglichen, die relevantesten bisher bekannten Tree-of-Tangles-Sätze als Korollare zu folgern. Die Voraussetzungen dieser Lemmata sind zudem leicht nachprüfbar und erlauben es, Tree-of-Tangles-Sätze für bestimmte Typen von abstrakten Teilungssystemen zu beweisen, für die solche Sätze bisher nicht bekannt waren. Sogar eine Anwendung außerhalb des Frameworks der abstrakten Teilungssysteme ist möglich: Wir folgern einen Tree-of-Tangles-Satz für Tangles von gerichteten Graphen aus einem der beiden Lemmata.

Zudem zeigen wir, dass die Konstruktion eines Tree-of-Tangles in einer größeren Allgemeinheit als bisher bekannt kanonisch, also invariant unter Isomorphismen durchgeführt werden kann. Bisher war so eine kanonische Konstruktion nur für submodulare Universen von Teilungen bekannt, wir zeigen, dass eine solche kanonische Konstruktion auch in strukturell submodularen Teilungssystemen möglich ist. In diesen Systemen war bisher nur ein nicht-kanonischer Tree-of-Tangles-Satz bekannt.

Zudem entwickeln wir eine Variante der oben angesprochenen Lemmata für unendliche Strukturen, welche es uns ermöglicht, Tree-of-Tangles-Sätze auch für solche unendlichen Strukturen zu beweisen. Dieses Lemma können wir zudem auf die Trenner eines unendlichen Graphen anstelle seiner Teilungen anwenden, was es uns ermöglicht zu zeigen, dass man diese Trenner verwenden kann, um einen unendlichen Graphen kanonisch, baumartig, entsprechend seiner Tangles zu zerlegen. Diese Zerlegung ist insbesondere deswegen interessant, weil wir sie sowohl verwenden können, um einen bekannten, nicht kanonischen Tree-of-Tangles-Satz zu beweisen, als auch, um die Existenz eines kanonischen "Baums von Baumzerlegungen" — ein anderes bekanntes Resultat über die Zerlegung unendlicher Graphen — zu folgern.

Zudem können wir unser Lemma über Trees-of-Tangles in unendlichen Strukturen verwenden, um einen unendlichen Graphen entsprechend seiner Kantenblöcke zu zerlegen. Ein Kantenblock ist hierbei ein maximaler Teilgraph, der nicht durch eine fixe Anzahl von Kanten getrennt werden kann.

Wir beenden Kapitel 4, indem wir zeigen, dass das andere klassische Resultat der Tangletheorie, der sogenannte Tangle-Tree-Dualitätssatz, dazu verwendet werden kann, einen Tree-of-Tangles-Satz zu beweisen. Dies zeigt, dass die bisher als unabhängig geltenden zwei zentralen Säulen der Tangletheorie — die Tree-of-Tangles-Sätze auf der einen und die Tangle-Tree-Dualitätssätze auf der anderen Seite — nicht so unabhängig voneinander sind wie man bisher dachte — schließlich kann man ein Resultat des einen Typs verwenden, um ein Resultat des anderen Typs zu folgern.

Im letzten Kapitel, Kapitel 5, dieser Dissertation untersuchen wir abstrakte Teilungssysteme als eigenständige Struktur. Zum einen zeigen wir, dass einige der existierenden verschiedenen Definitionen im Kontext dieser Systeme, nämlich zum Beispiel die oben erwähnten submodularen Universen von Teilungen und submodularen Teilungssysteme, in der Tat unterschiedliche Objekte beschreiben, indem wir entsprechende Beispiele konstruieren. Nachdem wir festgestellt haben, dass diese verschiedenen Definitionen in der Tat verschiedene Objekte beschreiben, untersuchen wir im nächsten Schritt, wie groß der Unterschied tatsächlich ist: verhalten sich die strukturell submodularen Teilungssysteme in gewissem Sinne "ähnlich" wie die submodularen Universen? Diese Analyse führt zum einen zu einem Zerlegungssatz für strukturell submodulare Teilungssysteme in distributiven Universen, zum anderen zu einer allgemeinen Frage über bestimmte Familien endlicher Mengen, die wir verwoben nennen. Unser Entwirrungsproblem, mit dem wir uns am Ende von Kapitel 5 beschäftigen, ist eine einfach zu formulierende Frage über diese verwobenen Mengen. Wir analysieren dieses Problem und lösen einige Varianten und Spezialfälle.