Games on Infinite Graphs and Structural Properties of Directed and Bidirected Graphs

Abstract

Games on Graphs:

In Part I we investigate (G,H)-games for different graphs G and H: two players alternately claim edges of a graph G with the aim to have a copy of H contained in the claimed edges. In the strong version of the game it is the aim of both players, in the Maker-Breaker version it is just the aim of Maker, while Breaker tries to prevent this. The main result of Chapter 3 is that there is a winning strategy for the first player in the strong K_4-game. In Chapter 4 we consider the Maker-Breaker game where it is Maker's aim to build a complete countably infinite graph with a number of different additional structural requirements. We prove that in the basic version of the game there is a winning strategy for Maker. A possible structural property is to colour the vertices of the board and require that Maker’s target graph H reflects the colouring of the board. We show that if there are only finitely many colours then Maker can obtain a complete subgraph in which all colours appear infinitely often, but that Breaker can prevent this if there are infinitely many colours. Even when there are infinitely many colours, we show that Maker can obtain a complete subgraph in which infinitely many of the colours each appear infinitely often. Another possible structural property is to enumerate the board with the rational numbers and require that the vertex set of Maker’s complete infinite graph with the induced ordering on the vertex set is order-isomorphic to the rationals. We prove that there is a winning strategy for Maker in this game in Section 4.4. We also prove that there is a winning strategy for Breaker in the game where Maker must additionally make the vertex set of her complete graph dense in the rationals. In Chapter 5 we investigate Maker-Breaker games with boards of the smallest uncountable cardinal in which Maker’s goal is to build a copy of the host graph. In contrast to the smaller boards, set-theoretic considerations come into play and a firm dependence of the outcome of the game on the axiomatic framework is established. We prove that there is a winning strategy for Maker in the game where Maker's aim is to complete a complete bipartite graph where one side has countable size and the other uncountable size, under ZFC+MA+¬CH and a winning strategy for Breaker under ZFC+CH. We prove a similar result for the game where it is Maker's aim to build a complete graph of the smallest uncountable cardinality. There, Maker has a winning strategy under ZF+DC+AD, while Breaker has one under ZFC+CH again.

Directed and Bidirected Graphs:

In Part II we study directed and bidirected graphs. We touch on different subjects in the field and prove a number of results. In Chapter 6 we investigate ubiquity in directed graphs by considering two simple classes of directed graphs: digraphs whose underlying undirected graph is a ray or a double ray. We prove that a digraph whose underlying undirected graph is a ray is ubiquitous if and only if it has only finitely many vertices of in-degree 2 as well as only finitely many vertices of out-degree 2. For a digraph whose underlying undirected graph is a double ray that is not a directed double ray we prove that it is ubiquitous if and only if the sum of the number of vertices of in-degree 2 and vertices of out-degree 2 is odd. In Chapter 7 we generalise a result by László Lovász. He proved that for any finite digraph D with a root r there is a spanning subdigraph L such that for every vertex v other than the root some maximal set of paths from r to v in L covers all incoming edges of v in D while one may choose from each path of such a maximal set of paths precisely one edge or internal vertex in such a way that the resulting set separates r from v in the original graph D. Attila Joó proved the corresponding statement for countably infinite digraphs. We prove the corresponding result for digraphs of the smallest uncountable cardinality. In Chapter 8 we investigate 1-separations in (possibly infinite) directed graphs. For this purpose we introduce a relation for tight set partitions, correspondence, and a novel structure called torsoids. We show that being in correspondence is an equivalence relation on a certain class of tight set partitions and obtain a good insight into how tight sets relate to torsoids. We further prove that if there is a torsoid corresponding to a tight set partition, it is unique. In summary, we show that torsoids are a global tool in the sense that they capture all tight cut contractions of a given digraph independent of the precise choice of a tight cut family. Lastly, in Chapter 9 we investigate connectivity in bidirected graphs, a generalisation of directed graphs. An important theorem in graph theory due to Karl Menger asserts that in a graph the maximum number of disjoint paths connecting two vertex sets X and Y in a graph is the same as the minimum number of vertices separating X and Y . Unfortunately this statement can not be moved verbatim to bidirected graphs, which we demonstrate. We also prove that there is a corresponding statement in bidirected graphs for which we introduce an additional property, cleanness. We also prove that there is a Menger type statement for edge disjoint paths in bidirected graphs and that both statements imply Menger’s Theorem in directed and undirected graphs. Our statement also gives a polynomial time algorithm to calculate a set of paths and a separating set of vertices.

Spiele auf Graphen:

In Teil I untersuchen wir (G, H)-Spiele für verschiedene Graphen G und H: zwei Spieler reklamieren abwechselnd Kanten eines Graphen G für sich, mit dem Ziel eine Kopie von H in den von ihnen eingenommenen Kanten zu enthalten. In der starken Variante des Spiels ist dies das Ziel beider Spieler, in der Erbauer-Zerstörer Variante ist dies lediglich das Ziel des Erbauers, während es das Ziel des Zerstörers ist, den Erbauer vom Erreichen seines Ziels abzuhalten. Das Hauptergebnis von Kapitel 3 ist, dass es eine Gewinnstrategie für den ersten Spieler in der starken Variante des K_4-Spiels gibt. In Kapitel 4 betrachten wir das Erbauer-Zerstörer Spiel, in dem es das Ziel des Erbauers ist, einen abzählbar unendlichen Graphen zu bauen, mit verschiedenen zusätzlichen strukturellen Anforderungen. Wir beweisen, dass es in der Grundversion des Spiels eine Gewinnstrategie für den Erbauer gibt. Eine mögliche strukturelle Eigenschaft ist, die Ecken des Spielfelds zu färben und zu verlangen, dass der Zielgraph H des Erbauers die Färbung des Spielfelds widerspiegelt. Wir zeigen, dass, wenn es nur endlich viele Farben gibt, der Erbauer einen vollständigen Teilgraphen erhalten kann, in dem alle Farben unendlich oft auftreten, aber dass der Zerstörer dies verhindern kann, wenn es unendlich viele Farben gibt. Für die Variante in der es unendlich viele Farben gibt, zeigen wir, dass der Erbauer einen vollständigen Teilgraphen erhalten kann, in dem unendlich viele verschiedene Farben jeweils unendlich oft auftreten. Eine weitere mögliche strukturelle Eigenschaft ist, das Spielfeld mit den rationalen Zahlen aufzuzählen und zu verlangen, dass die Eckenmenge des vollständigen unendlichen Graphen des Erbauers mit der induzierten Ordnung auf der Eckenmenge isomorph zu den rationalen Zahlen ist. Wir beweisen in Abschnitt 4.4, dass es eine Gewinnstrategie für den Erbauer in diesem Spiel gibt. Wir beweisen ebenfalls, dass es eine Gewinnstrategie für den Zerstörer in der Variante des Spiels gibt, in der die Eckenmenge des vollständigen Graphen des Erbauers dicht in den rationalen Zahlen sein muss. In Kapitel 5 untersuchen wir Erbauer-Zerstörer Spiele auf Spielfeldern der kleinsten überabzählbaren Kardinalität, in denen es das Ziel des Erbauers ist, eine Kopie des Spielfelds zu erstellen. Im Gegensatz zu den kleineren Spielfeldern sind hier mengentheoretische Aspekte relevant. Wir stellen fest, dass es eine starke Abhängigkeit des Spielausgangs vom axiomatischen Rahmen gibt. Wir beweisen, dass es eine Gewinnstrategie für den Erbauer in dem Spiel, in dem es das Ziel des Erbauers ist einen vollständigen bipartiten Graphen zu bauen, dessen eine Seite abzählbar unendlich ist und dessen andere Seite die kleinste überabzählbare Kardinalität hat. Unter ZFC+MA+¬CH und eine Gewinnstrategie für den Zerstörer unter ZFC+CH gibt. Wir beweisen ein ähnliches Ergebnis für das Spiel in dem es das Ziel des Erbauers ist, einen Graphen mit der kleinsten überabzählbaren Kardinalität zu vollenden. In diesem hat der Erbauer eine Gewinnstrategie unter ZF+DC+AD, während der Zerstörer eine unter ZFC+CH hat.

Gerichtete und Bigerichtete Graphen:

In Teil II untersuchen wir gerichtete und bigerichtete Graphen. Wir schneiden diverse Themen auf diesem Gebiet an und beweisen Ergebnisse in diesen verschiedenen Bereichen. In Kapitel 6 untersuchen wir Allgegenwart in gerichteten Graphen, indem wir zwei einfache Klassen von gerichteten Graphen betrachten: gerichtete Graphen, deren zugrundeliegender ungerichteter Graph ein Strahl oder ein Doppelstrahl ist. Wir beweisen, dass ein gerichteter Graph, dessen zugrunde liegender ungerichteter Graph ein Strahl ist, allgegenwärtig ist, genau dann, wenn er endlich viele Ecken mit Eingangsgrad 2 und endlich viele Ecken mit Ausgangsgrad 2 hat. Für einen gerichteten Graphen dessen zugrunde liegender ungerichteter Graph ein Doppelstrahl aber kein gerichteter Doppelstrahl ist, beweisen wir, dass er allgegenwärtig ist, genau dann, wenn die Summe der Anzahl der Ecken mit Eingangsgrad 2 und Ecken mit Ausgangsgrad 2 ungerade ist. In Kapitel 7 verallgemeinern wir ein Ergebnis von László Lovász. Er bewies, dass es für jeden endlichen gerichteten Graphen D mit designierter Wurzel r einen aufspannenden gerichteten Teilgraphen L gibt, so dass es für jede Ecke von der Wurzel verschiedene Ecke v eine maximale Menge von Wegen von r zu v in L gibt, die alle eingehenden Kanten von v in D überdeckt und, dass man aus jedem Weg einer solchen maximalen Menge von Wegen genau eine Kante oder interne Ecke auswählen kann, sodass die resultierende Menge im ursprünglichen Graph D die Wurzel r von der Ecke v trennt. Attila Joó bewies die entsprechende Aussage für abzählbar unendliche gerichtete Graphen. Wir beweisen das entsprechende Ergebnis für gerichtete Graphen der Kardinalität א1. In Kapitel 8 untersuchen wir 1-Separationen in (möglicherweise unendlichen) gerichteten Graphen. Zu diesem Zweck führen wir eine Relation zwischen Partitionen von knappen Mengen ein, welche wir Korrespondenz nennen, und wir definieren eine neue Struktur namens Torsoid. Wir zeigen, dass ”in Korrespondenz stehen“ eine äquivalenzrelation auf einer bestimmten Klasse von Partitionen von knappen Mengen ist und erhalten einen guten Einblick in die Interaktion von knappen Mengen mit Torsoiden. Wir beweisen außerdem, dass wenn ein Torsoid existiert, der in Korrespondenz zu einer Partition von knappen Mengen steht, dieser eindeutig ist. Zusammenfassend zeigen wir, dass Torsoide in dem Sinne ein globales Werkzeug sind und, dass sie alle Kontraktionen knapper Schnitte eines gegebenen gerichteten Graphen erfassen, unabhängig von der genauen Wahl einer Familie von knappen Schnitten. Zuletzt untersuchen wir in Kapitel 9 Zusammenhang in bigerichteten Graphen, einer Verallgemeinerung von gerichteten Graphen. Ein wichtiges Theorem der Graphentheorie von Karl Menger besagt, dass in einem Graphen die maximale Anzahl disjunkter Wege, die zwei Eckenmengen X und Y in einem Graphen verbinden, gleich der minimalen Anzahl von Ecken ist, die X und Y trennen. Wir beweisen, dass diese Aussage nicht direkt auf bigerichtete Graphen übertragen werden kann. Wir beweisen aber eine dazu passende Aussage in bigerichteten Graphen, für die wir eine zusätzliche Eigenschaft einführen: Sauberkeit. Wir zeigen dann eine mengerartige Aussage für kantendisjunkte Wege in bigerichteten Graphen für Eckenmengen, die sauber sind. Wir beweisen ebenfalls, dass sowohl die eckendisjunkte als auch die kantendisjunkte Aussage die jeweiligen nach Menger benannten Theoreme in gerichteten und ungerichteten Graphen implizieren. Zuletzt zeigen wir, dass unsere Aussage einen Polynomialzeitalgorithmus zur Berechnung einer Wegemenge und einer trennenden Eckenmenge liefert.