Maker-Breaker Games On Graphs

Abstract

In this thesis, we investigate Maker-Breaker games on graphs using two primary frameworks and review the accompanying literature to establish the necessary theoretical foundation. On one hand, we discuss our results on the Maker-Breaker directed triangle game on tournaments. Our study focuses on a particular tournament with a parity-based orientation rule that leads to explicit winning strategies for Breaker on smaller parity tournaments and a winning strategy for Maker on larger parity tournaments, with a threshold identified at $n=7$. We prove certain results regarding the biased variant of this game, and demonstrate Maker's win when the game is played on the uniform random tournament. We also propose a new kind of “bias”, called the \emph{flip bias }for Breaker in the directed triangle game, which is motivated by the effect of the score variance of vertices on the number of $3$-cycles in the tournament. On the other hand, we present results on the Maker-Breaker percolation game on infinite rooted trees, extending known findings by deriving a condition for Maker's win on $k$-periodic trees, and applying a strategic and adversarial exploration process approach to Galton-Watson trees. We also include a concise review of fundamental results in positional game theory to contextualize the topic. Collectively, the results discussed in this thesis provide a framework for understanding how graph structure influences winning strategies in Maker-Breaker games and suggest directions for future research.