On the Chvátal-Erdős Triangle Game
József Balogh, Wojciech Samotij · The Electronic Journal of Combinatorics · 2011
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2011
Abstract
Given a graph $G$ and positive integers $n$ and $q$, let ${\bf 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 ${\bf 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 ${\bf 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 $(\sqrt{2}+o(1))\sqrt{n}$.
Open the resolved locator · 10.37236/559
Metadata licence: OpenAlex metadata (CC0)