Path spaces

Abstract

In this dissertation we introduce path spaces, an infinitary generalization of graphs, which allows us to prove general statements for a variety of path-like objects, including topological arcs in Hausdorff spaces. We spend the rest of the dissertation proving results about them. This happens over the course of four chapters.

In Chapter 1 we consider general connectivity theory. By using different types of alternating paths, we prove two main results. The first is a version of Menger's theorem, showing that the maximum number disjoint of paths between two sets is equal to the minimum size of a separator assuming the first number is finite. The second result shows that we can find a similar duality, though with a more complex witness, for the maximum number of disjoint paths starting and ending in some set. This is a theorem of Gallai for graphs and corresponds to the base case of Mader's theorem.

In Chapter 2 we consider tree-like decompositions of path spaces, making use of the recent theory of separation systems. We begin with a decomposition of connected path spaces into blocks and a decomposition of 2-connected path spaces into 2-blocks, which are parts whose torsos are 3-connected or cycles. Then we move to general widths and use the concept of necklaces to show that every path space of high tree width contains a large grid minor.

In Chapter 3 we note that separations systems of path spaces are limit-closed and analyze in general limit-closed vertex separation systems. We start with a short proof that limit-closed profiles can distinguished by a tree set. Afterward we investigate the flowers of limit-closed separation systems and prove in particular the existence of maximal such objects.

In Chapter 4 we consider questions of ubiquity, more specifically we ask whether path spaces contain infinitely many disjoint copies of a certain substructure whenever they contain arbitrarily many disjoint copies. We first prove that cycles and more generally ladder-like structures are ubiquitous and then apply the grid theorem to show that this applies to minor embeddings of finite planar graphs more generally. We also talk about a notion of edge-ubiquity and show that cycles have this property.

Diese Dissertation führt Wegräume ein, eine Verallgemeinerung von Graphen, die unendliche Wege zulässt. Mithilfe dieser können wir Aussagen gleichzeitig für verschiedene wegartige Objekte beweisen, darunter topologische Bögen in Hausdorffräumen. Im weiteren Verlauf der Dissertation zeigen wir im Laufe von vier Kapiteln ebensolche Resultate.

In Kapitel 1 betrachten wir Zusammenhang im Allgemeinen. Wir verwenden zwei verschiedene Arten von alternierenden Wegen, um zwei Hauptresultate zu beweisen. Das erste ist eine Version des Satzes von Menger; wir beweisen genauer, dass die maximale Anzahl von disjunkten Wegen zwischen zwei Mengen gleich der minimalen Größe eines Trenners ist, wenn die erste Zahl endlich ist. Das zweite Resultat zeigt eine ähnliche Dualität, wenn auch mit einem komplizierteren Gegenpart, für die maximale Anzahl von disjunkten Wegen die in einer bestimmten Menge beginnen und enden. Für Graphen ist das ein Satz von Gallai, der dem Induktionsanfang vom Satz von Mader entspricht.

In Kapitel 2 betrachten wir baumartige Zerlegungen von Wegräumen, wobei wir die noch junge Theorie von Separationssytemen verwenden. Zunächst konstruieren wir Zerlegungen von zusammenhängenden Wegräumen in ihre Blöcke und von 2-zusammenhängenden Wegräumen in 2-Blöcke, das heißt Teile der Zerlegung deren Torsos 2-zusammenhängend oder Kreise sind. Danach verwenden wir Halsketten, um das zu zeigen, dass jeder Wegraum mit hoher Baumweite einen großen Gitterminor enthält.

In Kapitel 3 bemerken wir, dass Separationssysteme von Wegräumen unter Limites abgeschlossen sind und betrachten solche Separationssystem im Allgemeinen. Zunächst zeigen wir, dass Profile, die unter Limites abgeschlossen sind, durch eine geschachtelte Menge von Teilungen unterschieden werden können. Danach betrachten wir Blumen von Separationssystemen und zeigen unter anderem die Existenz von maximalen Blumen unter Annahme dieser Abschlußeigenschaft.

In Kapitel 4 untersuchen wir Ubiquität, das heißt wir fragen ob Wegräume, die beliebig viele disjunkte Kopien von bestimmten Unterstrukturen enthalten auch unendlich viele solche Kopien enthalten. Wir zeigen zunächst, dass Kreise und allgemeiner leiterartige Strukturen diese Eigenschaft haben und wenden dann den Gittersatz an um allgemeiner die Ubiquität von Einbettungen von endlichen, planaren Graphen als Minor zu beweisen. Weiterhin geben wir eine Definition von Kantenubiquität und zeigen, dass Kreise dies erfüllen.