Some Results on the Maker Breaker Triangle Game

Abstract

Positional games are a broad class of games with complete information. Given their practical and `real-world' origins, they have attracted constant attention from mathematicians working in combinatorics over the years. In this thesis, we study the Maker-Breaker triangle game played on a complete graph with $n$ vertices. Two players, Maker and Breaker, alternate turns claiming unclaimed edges: Maker selects one edge per turn, while Breaker claims $q$ edges. Maker wins the game if the edges he has claimed form a triangle; otherwise, Breaker wins. The objective is to figure out the `threshold' \(q_0(n)\) such that the Maker wins if \(q< q_0\) and the Breaker wins if \(q> q_0\) under `perfect play'. Finding out sharp bounds on the threshold \(q_0\) remains a challenging open problem. Erdos and Chavatal, showed that \(\sqrt{2n}\leqslant q_0(n)\leqslant 2\sqrt{n}\). Balogh and Samotij, improved the upper bound to \(q_0\leqslant 1.958 \sqrt{n}\) by providing a randomized strategy for Breaker's win. Recently, Glazik and Srivastav, further improved the upper bound to \(q_0(n)\leqslant 1.633\sqrt{n}\) by providing a completely deterministic strategy for the Breaker and using a potential method based analysis. In this thesis, we survey all these results. For such Maker-Breaker games, Erdos had a remarkable insight: the asymptotic threshold value under perfect play should be the same if the players played completely randomly. This insight has since motivated extensive research into games where both players make moves uniformly at random, as well as those where one player moves uniformly at random while the other employs strategic, rational decision-making to optimize their chances of winning. While the above-mentioned paradigm holds true for the triangle game, and the threshold for the RandomMaker vs CleverBreaker game was also resolved asymptotically, the CleverMaker vs RandomBreaker triangle game was never studied explicitly. In this thesis, we address this gap in the literature, and, using standard probability techniques, show that in a CleverMaker vs RandomBreaker game, the following is true. If \({q=o(n^2)}\), then the CleverMaker has a strategy that wins with high probability. For all positive constants \(c,\) if \({q=cn^2},\) then the RandomBreaker wins with a positive constant probability.