In this dissertation we study tangles in graphs and in abstract separation systems. Tangles have their roots in graph theory, where they were employed to unify various notions of clusters and connectivity into a single general-purpose framework. Fundamentally tangles differ from previous concepts of connectivity by not imposing certain conditions on some vertex sets, but instead by setting up a system of separations to point towards the cohesive region, following certain consistency axioms.
These separations and their consistency properties can be formulated and studied outside of graph theory as well, making tangles applicable to a wide range of combinatorial structures. Most of the results presented in this work are set in this abstract framework. However, many of our applications will still feature graphs.
This work is divided into three main chapters, Chapters 3 to 5. In Chapter 3 we seek to find out in which ways abstract separation systems differ from known instances of separations such as separations of graphs or bipartitions of sets. For this we provide combinatorial characterisations of those classical types of separations. With these results one can now tell when a given abstract separation system is actually an instance of a well-known type of separations. On the other hand we construct examples of separation systems with a structure that is fundamentally different from any classical type.
We also investigate submodular separation systems: those embeddable in some lattice in such a way that they contain either the meet or the join of any two of their elements. This submodularity is used in many places in tangle theory, including in our later chapters. We show that submodularity can be studied without an a priori lattice structure, which can then be added a posteriori if desired. We also show that certain types of submodular separation systems always admit a separation whose deletion leaves the system submodular.
In Chapter 4 we present results in finite tangle theory. The two archetypes for results in this field are tree-of-tangles theorems and tangle-tree duality theorems. The first type asserts that if a structure has many tangles, then they can be neatly separated from each other in a tree-like structure. The second says that if a structure has no tangles, then the structure itself has a tree-like shape which certifies this. We improve upon the state of the art for both types of results.
Regarding tree-of-tangles theorems we identify the core engine of this ar- chetype and prove an elementary and flexible theorem with a compact proof that, as we go on to show, implies virtually all previously known tree-of-tangles theorems. Our results comes with an easy-to-check sufficient condition which makes the derivations of classical results from ours routine. We also use our result to establish tree-of-tangles theorems in settings where this was previously impossible.
As for the tangle-tree duality theorem we improve upon Diestel’s and Oum’s [19] by giving a new proof of their tangle-tree duality theorem which is not only shorter and conceptually clearer, but also yields a stronger result. In fact we offer two new proofs of this strengthened theorem: both of them follow similar concepts, with the first focusing on brevity and the second on eliminating technical preliminaries. We also show that this tangle-tree duality theorem can be used to establish a tree-of-tangles theorem, demonstrating that these two archetypes of tangle-theoretical results are not as disjoint as they might at first seem. This new technique of constructing a tree of tangles also allows one to obtain bounds on the degrees in that tree, something which previous methods of building trees of tangles are not able to do.
We close Chapter 4 by substantiating the intuition that tangles in graphs point towards clusters or highly cohesive regions. For this we answer a fractional version of a question by Diestel, who asked whether there is for each tangle in a graph a set of vertices such that each separation in the tangle is oriented towards the side containing the majority of those vertices. Using techniques from linear programming we show that this is true with a weighted set of vertices.
Finally, in Chapter 5 we investigate tangles in infinite graphs and abstract separation systems. Every end of an infinite graph defines a tangle of all separations of finite order; we can thus study the properties of ends thorough the tangles they define. The separation system of an infinite graph can be equipped with a natural topology. We give a combinatorial characterisation of those ends which define tangles that are closed in this topology. One of the equivalences we establish calls back to the last part of Chapter 4: the closed end tangles are those decided by majority vote by a finite set of vertices.
We then turn to tree-of-tangle theorems in infinite separation systems. Our core result from Chapter 4 relies on induction and thus fails in an infinite setting. Nevertheless, using the topology from above, we provide a way in which that result can be extended to infinite abstract separation systems. As an application of this we prove a tree-of-tangles theorem for infinite graphs.
In dieser Dissertation widmen wir uns Tangles in Graphen und in abstrakten Teilungssystemen. Tangles entstammen der Graphentheorie, wo sie eingesetzt wurden um verschiedene Konzepte von Clustern und Zusammenhang zu einem einzigen allgemeinen Ansatz zu vereinen. Tangles unterscheiden sich von bisherigen Zusammenhangskonzepten fundamental dadurch dass sie nicht eine Liste von Bedingungen an gewisse Eckenmengen stellen, sondern stattdessen ein System von Teilungen sind, welche in Richtung der hochzusammenhängenden Region des Graphen deuten und gewissen Konsistenzbedingungen unterliegen.
Diese Teilungen und ihre Konsistenzeigenschaften können auch losgelöst von der Graphentheorie betrachtet und studiert werden, wodurch Tangles auf eine große Bandbreite kombinatorischer Strukturen anwendbar werden. Die meisten der in dieser Arbeit vorgestellten Resultate sind in dieser abstrakten Art formuliert; nichtsdestotrotz sind viele unserer Anwendungen immer noch Graphen
Die vorliegende Arbeit besteht aus drei Hauptkapiteln, Kapitel 3 bis 5. In Kapitel 3 wollen wir herausfinden inwieweit sich abstrakte Teilungssyteme von den bisher bekannten Arten von Teilungen wie Graphenteilungen oder Bipartitionen unterscheiden können. Hierfür führen wir eine kombinatorische Charakterisierung dieser klassischen Teilunstypen durch. Mit diesen Ergebn- issen kann man nun feststellen ob ein gegebenes abstraktes Teilungssystem in Wahrheit eine Instanz eines altbekannten Typs von Teilungen ist. Andererseits konstruieren wir Beispiele von Teilungssystemen mit fundamentalen strukturellen Unterschieden zu den klassischen Art von Teilungen.
Wir untersuchen auch submodulare Teilungssyteme: Solche welche so in einen Verband eingebettet werden können, dass sie für je zwei ihrer Elemente jeweils deren Supremum oder Infimum ebenfalls enthalten. Diese Submodularität taucht in der Tangle-Theorie an den verschiedensten Stellen auf und begegnet auch uns in dieser Arbeit mehrmals. Wir zeigen dass Submodularität auch ohne eine a priori existierende Verbandsstruktur studiert werden kann, wobei diese Verbandsstruktur nach Wunsch doch noch a posteriori hinzugefügt werden kann. Wir zeigen weiterhin dass bestimmte Arten solcher submodularen Teilungssyteme immer eine Teilung enthalten nach deren Löschen das Teilungssystem immer noch submodular ist.
In Kapitel 4 präsentieren wir unsere Ergebnisse in der endlichen Tangle-Theorie. Die zwei Grundtypen von Sätzen hier sind die Baum-von-Tangles-Sätze und die Tangle-Baum-Dualitätssätze. Erstere besagen dass in einer Struktur mit mehreren Tangles diese in einer baumartigen Weise voneinander getrennt werden können. Letzere Art von Satz besagt dass eine Struktur welche kein Tangle besitzt selbst eine baumartige Form haben muss, an der man dies ablesen kann. Wir präsentieren neue Ansätze für beide Arten von Sätzen.
Für die Baum-von-Tangles-Sätze identifizieren wir die zentrale Wirkungsweise dieser Art von Satz und beweisen damit einen elementaren und flexiblen Satz mit kurzem Beweis welcher, wie wir dann zeigen, nahezu alle bisher existier- enden Baum-von-Tangles-Sätze impliziert. Unser Ergebnis nutzt eine einfach zu überprüfende hinreichende Bedingung, wodurch das Ableiten der klassischen Resultate aus unserem zur Routine wird. Wir nutzen unseren Satz auch um neuartige Baum-von-Tangles-Sätze zu beweisen, gerade in Situationen in denen dies bisher nicht möglich war.
Zum Tangle-Baum-Dualitätssatz: Hier verbessern wir Diestels und Oums [19], indem wir einen neuen Beweis für ihren Satz präsentieren, welcher nicht nur kürzer und konzeptuell klarer ist, sondern auch eine stärkere Aussage ermöglicht. Tatsächlich geben wir sogar die Wahl zwischen zwei neuen Beweisen dieses verstärkten Resultats. Beide nutzen ähnliche Konzepte, wobei der erste Beweis auf Kürze ausgelegt ist und der zweite darauf das Prüfen von technischen Vorbedingungen zu eliminieren. Wir zeigen außerdem dass dieser Tangle-Baum- Dualitätssatz genutzt werden kann um einen Baum-von-Tangles-Satz zu beweisen. Die zwei Grundtypen von Sätzen in der Tangle-Theorie sind demnach nicht so verschieden wie es zunächst den Anschein hat. Diese neue Methode um einen Baum von Tangles zu konstruieren ermöglicht es zudem Schranken an die Grade der Ecken in diesem Baum zu erhalten; dies war mit den herkömmlichen Ansätzen zu Bäumen von Tangles nicht möglich.
Wir schließen Kapitel 4 damit ab die Intuition zu untermauern dass Tangles in Graphen auf Cluster oder hochzusammenhängende Regionen zeigen. Hierfür beantworten wir eine fraktionelle Version einer Frage von Diestel: Gibt es für jeden Tangle in einem Graphen eine Menge von Ecken, sodass jede Teilung in dem Tangle auf genau diejenige ihrer Seiten zeigt welche die Mehrheit dieser ausgewählten Ecken enthält? Unter Nutzung von Techniken aus dem linearen Programmieren zeigen wir dass dies mit einer gewichteten Menge von Ecken stimmt.
Schließlich kommen wir in Kapitel 5 zu Tangles in unendlichen Graphen und Teilungssystemen. Jedes Ende eines unendlichen Graphen definiert ein Tangle all seiner Teilungen endlicher Ordnung; wir können also die Eigenschaften von Enden studieren indem wir die von ihnen definierten Tangles analysieren. Das Teilungssystem eines unendlichen Graphen kann auf natürliche Art und Weise mit einer Topologie ausgestattet werden. Wir finden eine kombinatorische Charakterisierung derjenigen Enden deren Tangles in dieser Topologie abgeschlossen sind. Eine der Äquivalenzen, die wir hierbei zeigen, hängt mit dem letzten Teil von Kapitel 4 zusammen: Die abgeschlossenen Tangles von Enden sind genau diejenigen die von einer endlichen Eckenmenge durch Mehrheitsentscheid definiert werden.
Zuletzt widmen wir uns Baum-von-Tangles-Sätzen in unendlichen Teilungssystemen. Unser zentrales Ergebnis aus Kapitel 4 hierzu verwendet Induktion und scheitert daher im Unendlichen. Unter Nutzung der obigen Topolgie können wir dennoch einen Weg aufzeigen wie dieses Ergebnis auf unendliche abstrakte Teilungssysteme erweitert werden kann. Als Anwendung hiervon zeigen wir einen Baum-von-Tangles-Satz für unendliche Graphen.