2025/10/15 by Jagtap, Hrishikesh, Podder, Moumanti
#05C20 #05C57 #05C80 #91A24 #91A43 #91A46 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2510.13919
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 constitute all directed triangles (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 if the size (i.e. the number of vertices) of the parity tournament equals n, Breaker has a winning strategy for 3≤ n< 7, while Maker can ensure a win for herself for n≥ 7. For the (1:b) biased version of this game, we prove that the bias threshold b^*(n) satisfies √((1/12+o(1)) n)≤ b*(n) ≤√((8/3+o(1)) n), which matches the order of magnitude ( √(n)) of the bias threshold for the undirected counterpart of this game. Next, we consider the game on random tournaments T(n,p) with labeled vertices 1,2,…,n, such that the edge between i and j, for each i