Connectivity and tree structure in infinite graphs and digraphs

Abstract

This dissertation deals with different aspects of connectivity and tree structure in infinite graphs, which make it part of the research area of structural infinite graph theory. It consists of two parts: simple graphs are considered in Part I, and directed graphs, or digraphs, are considered in Part II. Part I consists of Chapters 2, 3 and 4, while Part II consists of Chapters 5 and 6. A typical theme of this research area are duality theorems that offer a dichotomy between the existence of some ‘highly connected part’ in a graph with the nonexistence of some tree-decomposition of that graph which, whenever it exists, clearly precludes the existence of such a ‘highly connected part’. In infinite graphs such tree-decompositions may not exist for other reasons. Hence, the notion of a nested separation system, has turned out to be useful for generalisations of the aforementioned type of duality theorem to infinite graphs. In Chapter 2 we work with tree sets, a more abstract version of these nested separation systems, and characterise the tree sets that can be represented as infinite graph-theoretic trees. Moreover, we introduce the notion of tree-like spaces, a special form of a graph-like space which exhibits many of the analogous properties that graph-theoretical trees exhibit. We then give a construction how regular tree sets can be represented by tree-like spaces and vice versa. In Chapter 3 we deal with a different aspect of connectivity by looking at ends of infinite graphs. An interesting property of the rays in a normal spanning tree of a graph is that every ray in an end meets the normal ray corresponding to that end in the normal spanning tree. A ray with this property is called end-devouring. Georgakopoulos introduced this concept for finite families of disjoint rays and proved their existence with some feasible set of prescribed start vertices. We answer a question of Georgakopoulos about the existence of a countable end-devouring family of disjoint rays in ends of countable degree where we can prescribe some feasible set of start vertices in that chapter. Chapter 4 is dedicated to the investigation of one aspect of higher connectivity, the k-connected sets for some positive integer k. In the spirit of the duality theorems mentioned earlier we prove the equivalence of the existence of a k-connected set of a certain cardinality kappa with the non-existence of a tree set in that graph of width less than kappa and adhesion less than k, which, whenever it exists, preclude the existence of such a k-connected set. Moreover, we characterise these k-connected sets via the existence certain minors (or topological minors). For fixed k and cardinal kappa there are only finitely many such (topological) minors. Both these results extend similar theorems of Geelen and Joeris in finite graphs. In Chapter 5 we investigate an extension of Edmonds’ Branching Theorem to locally finite digraphs. Similar to how in undirected locally finite graphs the topological framework developed by Diestel an his research group proved to be useful for an extension of tree-packing results (which fail in their straightforward generalisation as shown by Aharoni and Thomassen), we prove some facts about the topological setting in locally finite digraphs and extend a corresponding packing result for pseudo-arborescences, which we introduce here. Furthermore, we study the structure of these pseudo-arborescences as well. The last chapter, Chapter 6, introduces a conjecture of Heuer which, if affirmed, generalises a min-max theorem of Lucchesi and Younger that the maximum number of disjoint dicuts in a digraph equals the minimum size of a dijoin, i.e. an edge set meeting every dicut. The conjecture states that a structural version of this theorem that restricts itself to finite dicuts in an infinite graph still holds. We prove a reduction of this conjecture to countable digraphs whose underlying multigraph is 2-connected. Lastly, we affirm the conjecture in a variety of special cases.

Diese Dissertation behandelt verschiedene Aspekte von Zusammenhang und Baumstruktur in unendlichen Graphen. Als solche ist sie im Forschungsbereich der strukturellen unendlichen Graphentheorie einzuordnen. Sie besteht aus zwei Teilen, wobei Teil I sich mit einfachen Graphen und Teil II sich mit gerichteten Graphen beschäftigt. Teil I besteht aus den Kapiteln 2, 3 und 4, während Teil II aus den Kapiteln 5 und 6 besteht. Eine typische Ausprägung dieses Forschungsgebietes sind Dualitätssätze die eine Dichotomie zwischen der Existenz von bestimmten ‘hoch zusammenhängenden Teilen’ in einem Graphen und der nicht-Existenz einer Baumzerlegung herstellt, die, wenn sie existiert, offenbar die Existenz solcher ‘hoch zusammenhängender Teile’ ausschließt. In unendlichen Graphen können solche Baumzerlegungen allerdings auch aus anderen Gründen nicht existieren. In Folge dessen hat sich der Begriff des geschachtelten Teilungssystems als hilfreich herausgestellt, um solche Dualitätssätze vom Endlichen ins Unendliche zu generalisieren. In Kapitel 2 arbeiten wir mit Baummengen, einer abstrakten Version solcher geschachtelten Teilungssysteme, und Charakterisieren die Baummengen, die als unendliche graphentheoretischen Bäume repräsentiert werden können. Außerdem führen wir den Begriff des baumartigen Raumes ein, eine bestimmte Form von graphenartigen Räumen, die viele analoge Aspekte von graphentheoretischen Bäumen ausweisen. Dann geben wir eine Konstruktion an, wie reguläre Baummengen als solche baumartigen Räume dargestellt werden können, und umgekehrt. In Kapitel 3 betrachten wir ein anderen Aspekt von Zusammenhang, indem wir uns Enden von unendlichen Graphen anschauen. Eine interessante Eigenschaft von Strahlen in normalen Spannbäumen ist, dass jeder Stahl in einem Ende den normalen Stahl im normalen Spannbaum, der zu dem Ende gehört, trifft. Wir sagen, dass so ein Stahl das Ende verschlingt. Georgakopoulos hat dieses Konzept auf endliche Familien von disjunkten Strahlen erweitert und die Existenz solcher Familien mit einer realisierbaren vorgeschriebenen Menge von Startecken gezeigt. In diesem Kapitel beantworteten wir eine Frage von Georgakopoulos über die Existenz von abzählbaren endenverschlingenden Familien disjunkter Stahlen in Enden mit abzählbarem Grad, wobei wir auch hier eine realisierbare Menge von Startecken vorschreiben können. Kapitel 4 ist einem Aspekt von höherem Zusammenhang gewidmet, nämlich k-zusammenhängenden Mengen für eine positive natürliche Zahl k. Im Sinne der zuvor beschriebenen Dualitätssätze zeigen wir die Äquivalenz der Existenz einer k-zusammenhängenden Menge von Kardinalität Kappa mit der nicht-Existenz einer Baummenge mit Weite kleiner als Kappa und Adhäsion kleiner als k, welche, wenn sie existiert, die Existenz einer solchen k-zusammenhängenden Menge ausschließt. Außerdem charakterisieren wir k-zusammenhängende Mengen via bestimmter Minoren, beziehungsweise topologischer Minoren. Für festes k und Kardinalität Kappa haben wir nur endlich viele solcher Minoren, die auftreten können. Beide Resultate erweitern Theoreme von Geelen und Joeris über endliche Graphen. In Kapitel 5 untersuchen wir eine Erweiterung von Edmonds’ Arboreszenzpackungssatz in lokal endliche Digraphen. Im ungerichteten Fall hat sich die topologische Herangehensweise, die von Diestel und seiner Arbeitsgruppe entwickelt wurde, als hilfreich herausgestellt um Baumpackungssätze ins lokal endliche zu erweitern (dessen direkte Verallgemeinerung fehlschlägt, wie Aharoni und Thomassen gezeigt haben). Wir zeigen einige Fakten über diese topologische Herangehensweise in lokal endlichen Digraphen und beweisen ein Packungssatz über Pseudoarboreszenzen, die wir hier einführen. Ferner untersuchen wir die Struktur dieser Pseudoarboreszenzen. Im letzten Kapitel, Kapitel 6 stellen wir eine Vermutung auf, die, falls bestätigt ein Min-Max Theorem von Lucchesi und Younger, welches aussagt, dass die maximale Anzahl gerichteter Schnitte in einem Digraphen gleich der kleinsten Größe einer Menge ist, die alle diese gerichteten Schnitte überdeckt. Wir vermuten, dass eine strukturelle Version dieses Theorems, dass sich auf endliche gerichtete Schnitte beschränkt, auch in unendlichen Digraphen wahr ist. Wir zeigen, dass wir uns für den Beweis dieser Vermutung auf abzählbare Digraphen, dessen unterliegender Multigraph 2-zusammenhängend ist, beschränken können. Letztlich beweisen wir die Vermutung in diversen Spezialfällen.