Chasing the Threshold Bias of the 3-AP Game


الملخص بالإنكليزية

In a Maker-Breaker game there are two players, Maker and Breaker, where Maker wins if they create a specified structure while Breaker wins if they prevent Maker from winning indefinitely. A $3$-AP is a sequence of three distinct integers $a, b, c$ such that $b-a = c-b$. The $3$-AP game is a Maker-Breaker game played on $[n]$ where every round Breaker selects $q$ unclaimed integers for every Makers one integer. Maker is trying to select points such that they have a $3$-AP and Breaker is trying to prevent this. The main question of interest is determining the threshold bias $q^*(n)$, that is the minimum value of $q=q(n)$ for which Breaker has a winning strategy. Kusch, Rue, Spiegel and Szabo initially asked this question and proved $sqrt{n/12-1/6}leq q^*(n)leq sqrt{3n}$. We find new strategies for both Maker and Breaker which improve the existing bounds to [ (1+o(1))sqrt{frac{n}{5.6}} leq q^*(n) leq sqrt{2n} +O(1). ]

تحميل البحث