The Maker-Breaker directed triangle game
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908972232998912 |
|---|---|
| author | Jagtap, Hrishikesh Podder, Moumanti |
| author_facet | Jagtap, Hrishikesh Podder, Moumanti |
| contents | 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\ge7$. For the $(1:b)$ biased version of this game, we prove that the bias threshold $b^*(n)$ satisfies $\sqrt{\left(1/12+o(1)\right)n}\le b^*(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 $κ(n)$, where Breaker may strategically flip the directions of at most $κ(n)$ edges before the game begins. We show that the flip-bias threshold $κ^*(n)$ for this game is of order $n^2$. More precisely, for odd $n\ge11$ we show $n(n-11)/12\leκ^*(n)\le (n^2-1)/8$, and for even $n\ge14$ we show $n(n-14)/12+1\leκ^*(n)\le n^2/8+n/4-1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_13919 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Maker-Breaker directed triangle game Jagtap, Hrishikesh Podder, Moumanti Combinatorics Probability 05C57, 91A24, 05C20, 05C80, 91A43, 91A46 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\ge7$. For the $(1:b)$ biased version of this game, we prove that the bias threshold $b^*(n)$ satisfies $\sqrt{\left(1/12+o(1)\right)n}\le b^*(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 $κ(n)$, where Breaker may strategically flip the directions of at most $κ(n)$ edges before the game begins. We show that the flip-bias threshold $κ^*(n)$ for this game is of order $n^2$. More precisely, for odd $n\ge11$ we show $n(n-11)/12\leκ^*(n)\le (n^2-1)/8$, and for even $n\ge14$ we show $n(n-14)/12+1\leκ^*(n)\le n^2/8+n/4-1$. |
| title | The Maker-Breaker directed triangle game |
| topic | Combinatorics Probability 05C57, 91A24, 05C20, 05C80, 91A43, 91A46 |
| url | https://arxiv.org/abs/2510.13919 |