Two-player games on graphs

Abstract

In this thesis we study different kinds of combinatorial games between two players, which are played on a board that consists of the edges of some given graph G. We distinguish unbiased games, in which both players claim/orient one edge in each round, and b-biased games in which the second player claims/orients b edges in each round. The first game in this regard is the strict oriented-cycle game, which was introduced by Bollobás and Szabó, and later studied by Ben-Eliezer, Krivelevich and Sudakov. It is played by OMaker and OBreaker, who assign orientations to the edges of the complete graph K_n alternately. OMaker has the goal to create a directed cycle, while OBreaker wants to prevent such. It has been asked by Bollobás and Szabó to find the largest value b for which OMaker has a winning strategy in the b-biased strict oriented-cycle game, i.e. when OBreaker orients b edges in each round. They conjectured this value to be n-3, which turned out to be false, when, in an earlier work with Liebenau, we were able to show an upper bound of size n-c\sqrt{n}. In this thesis we improve on this bound, and we show that even for b> 37n/40 OBreaker has a strategy to prevent cycles. The second game is the tournament game, which was introduced by Beck. Here, TMaker and TBreaker, alternately claim edges of a given graph G, where TMaker additionally assigns orientations to her edges. She wins, if her directed graph contains at least one copy of a pre-defined tournament T, while TBreaker wins otherwise. We consider this game when G is the complete graph K_n or a random graph sampled according to the random graph model G_{n,p}, whereas T is a tournament on a constant number k of vertices. We study thresholds for the bias b and the probability p around which a TMaker's win suddenly turns into a TBreaker's win. As third, we study the tree embedding game, which belongs to the family of Maker-Breaker games. The latter became very popular throughout the last decades, as many researchers, including Beck, Bednarska, Erdös, Hefetz, Krivelevich, Luczak, Stojakovic and Szabó, contributed to this field. The tree embedding game is played as follows: Maker and Breaker alternately claim edges of the complete graph K_n, where each player claims exactly one edge per round. Maker wins if, by the end of the game, her edges contain a copy of some pre-defined spanning tree T; Breaker wins otherwise. For large n, we show that Maker has a strategy to win within n+1 rounds, in case the maximum degree of T is bounded by a constant. Studying random trees, we also show that for almost every choice of T, Maker wins the game within n-1 rounds. Finally, we consider Walker-Breaker games, as they were introduced by Espig, Frieze, Krivelevich and Pegden. Walker and Breaker alternately choose edges of K_n, but with the constraint that Walker has to choose her edges according to a walk. We discuss some questions of Espig et. al. In particular, we determine how large cycles Walker can create.

In dieser Dissertation werden kombinatorische Spiele auf Graphen mit zwei Spielern studiert. Der erste Spieler beansprucht/orientiert stets genau eine Kante des gegebenen Graphen pro Runde, während der zweite Spieler b Kanten wählt. Wir betrachten das „strict oriented-cycle game“, welches von Bollobás und Szabó definiert wurde. OMaker und OBreaker orientieren hierbei abwechselnd die Kanten des vollständigen Graphen K_n, wobei OMaker genau dann gewinnt, wenn ein gerichteter Kreis entsteht. Entgegen einer Vermutung von Bollobás und Szabó zeigten wir kürzlich in einem Projekt mit Liebenau, dass OBreaker eine Gewinnstrategie besitzt, falls b> n-c\sqrt{n} gilt. In dieser Arbeit verbessern wir diese Schranke und zeigen, dass er sogar gewinnt, wenn b> 37n/40. Als zweites untersuchen wir das „tournament game“, welches von Beck motiviert wurde. Wieder orientieren zwei Spieler, TMaker und TBreaker, abwechselnd die Kanten eines gegebenen Graphen G, wobei TMaker genau dann gewinnt, wenn ihre Kanten eine Kopie eines gegebenen Turniers T mit k Ecken induzieren. Wir bestimmen Schwellenwerte für den „bias“ b, hinsichtlich der Eigenschaft, dass der erste Spieler eine Gewinnstrategie auf G=K_n besitzt. Falls G ein Zufallsgraph mit n Ecken und Kanten-Wahrscheinlichkeit p ist, bestimmen wir zudem entsprechende Schwellenwerte für die Wahrscheinlichkeit p. Mit dem „tree embedding game“ untersuchen wir schließlich ein Spiel, das zu den klassischen „Maker-Breaker“-Spielen gehört, welche unter anderem von Beck, Erdös, Hefetz, Krivelevich, Stojakovic und Szabó studiert wurden. In diesem Spiel nehmen beide Spieler, Maker und Breaker, abwechselnd jeweils genau eine Kante von K_n ein, wobei Maker das Ziel verfolgt, mit ihren Kanten eine Kopie eines aufspannenden Baums T zu erzeugen. Wir zeigen, dass sie dieses Ziel für große n stets in n+1 Runden erreichen kann, falls der Maximalgrad von T durch eine Konstante beschränkt ist. Falls T ein zufälliger aufspannender Baum ist, zeigen wir zudem, dass sie mit hoher Wahrscheinlichkeit innerhalb von n-1 Runden gewinnen kann. Schließlich betrachten wir „Walker-Breaker“-Spiele, in denen Walker und Breaker abwechselnd Kanten des vollständigen Graphen K_n einnehmen, aber mit der Einschränkung, dass die Kanten von Walker einen Kantenzug bilden. Bezugnehmend auf Fragen von Espig, Frieze, Krivelevich und Pegden zeigen wir unter anderem, welche Kreise Walker erzeugen kann.