FAQ
© 2019 Staats- und Universitätsbibliothek
Hamburg, Carl von Ossietzky

Öffnungszeiten heute09.00 bis 24.00 Uhr alle Öffnungszeiten

Eingang zum Volltext in OPUS

Hinweis zum Urheberrecht

Dissertation zugänglich unter
URN: urn:nbn:de:gbv:18-99171
URL: http://ediss.sub.uni-hamburg.de/volltexte/2019/9917/


Connectivity and tree structure in infinite graphs and digraphs

Zusammenhang und Baumstruktur in unendlichen Graphen und Digraphen

Gollin, Jochen Pascal

pdf-Format:
 Dokument 1.pdf (1.524 KB) 


SWD-Schlagwörter: Graphentheorie , Unendlicher Graph , Gerichteter Graph , Topologische Graphentheorie
Freie Schlagwörter (Deutsch): Strukturelle Graphentheorie
Freie Schlagwörter (Englisch): graph theory , infinite graph , directed graph , topological graph theory , structural graph theory
Basisklassifikation: 31.12
Institut: Mathematik
DDC-Sachgruppe: Mathematik
Dokumentart: Dissertation
Hauptberichter: Diestel, Reinhard (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 17.07.2019
Erstellungsjahr: 2019
Publikationsdatum: 14.08.2019
Kurzfassung auf Englisch: 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.
Kurzfassung auf Deutsch: 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.

Zugriffsstatistik

keine Statistikdaten vorhanden
Legende