On the Chvàtal-Erdős triangle game (Q540061)

Summary: Given a graph \(G\) and positive integers \(n\) and \(q\), let \(G(G; n, q)\) be the game played on the edges of the complete graph \(K_n\) in which the two players, Maker and Breaker, alternately claim 1 and \(q\) edges, respectively. Maker's goal is to occupy all edges in some copy of \(G\); Breaker tries to prevent it. In their seminal paper on positional games, Chvátal and Erdős proved that in the game \(G(K_3; n, q)\), Maker has a winning strategy if \(q < \sqrt{2n + 2} - 5/2\), and if \(q \geq 2 \sqrt n\), then Breaker has a winning strategy. In this note, we improve the latter of these bounds by describing a randomized strategy that allows Breaker to win the game \(G(K_3; n, q)\) whenever \(q \geq (2 - 1/24)\sqrt n\). Moreover, we provide additional evidence supporting the belief that this bound can be further improved to \(\left(\sqrt 2 + o(1)\right)\sqrt n\).