The Maker-Breaker directed triangle game

Abstract

In this work, we investigate Maker-Breaker directed triangle games, a directionally constrained variant of the classical Maker-Breaker triangle game. Our board of interest is a tournament, and the winning sets are all $3$-cycles present in the tournament. We begin by studying the Maker-Breaker directed triangle game played on a specially defined tournament called the parity tournament, and we identify the board size threshold to be $n=7$, which is to say that for a parity tournament on $n$ vertices, Breaker has a winning strategy for $3\le n<7$, while Maker can ensure a win for herself for $n\ge 7$. For the $(1:b)$ biased version of this game, we prove that the bias threshold $b^{\ast }(n)$ satisfies $\sqrt{\left(1/12+o(1)\right)n}\le b^{\ast }(n)\le \sqrt{\left(8/3+o(1)\right)n}$, which matches the order of magnitude, namely $\sqrt{n}$, of the bias threshold for the undirected counterpart of this game. Next, we consider the game on random tournaments $T(n,p)$, wherein the edge between $i$ and $j$, for each $i<j$, is directed from $i$ to $j$ with probability $p$, independent of all else. We prove that Maker wins this game with probability tending to $1$ as $n\to \infty$ for any fixed $p\in (0,1)$. Extending the notion of bias from undirected games to our directed framework, we introduce the flip-biased Maker-Breaker directed triangle game on the parity tournament with flip budget $\hat{I}º(n)$, where Breaker may strategically flip the directions of at most $\hat{I}º(n)$ edges before the game begins. We show that the flip-bias threshold $\hat{I}{º}^{\ast }(n)$ for this game is of order $n^2$. More precisely, for odd $n\ge 11$ we show $n(n-11)/12\le \hat{I}{º}^{\ast }(n)\le (n^2-1)/8$, and for even $n\ge 14$ we show $n(n-14)/12+1\le \hat{I}{º}^{\ast }(n)\le n^2/8+n/4-1$.