pith. sign in

arxiv: 1803.03793 · v2 · pith:YEL35V6Mnew · submitted 2018-03-10 · 🧮 math.CO

The Maker-Breaker Rado game on a random set of integers

classification 🧮 math.CO
keywords gamemakerbreakerclassintegersdimensioninteger-valuedmaker-breaker
0
0 comments X
read the original abstract

Given an integer-valued matrix $A$ of dimension $\ell \times k$ and an integer-valued vector $b$ of dimension $\ell$, the Maker-Breaker $(A,b)$-game on a set of integers $X$ is the game where Maker and Breaker take turns claiming previously unclaimed integers from $X$, and Maker's aim is to obtain a solution to the system $Ax=b$, whereas Breaker's aim is to prevent this. When $X$ is a random subset of $\{1,\dots,n\}$ where each number is included with probability $p$ independently of all others, we determine the threshold probability $p_0$ for when the game is Maker or Breaker's win, for a large class of matrices and vectors. This class includes but is not limited to all pairs $(A,b)$ for which $Ax=b$ corresponds to a single linear equation. The Maker's win statement also extends to a much wider class of matrices which include those which satisfy Rado's partition theorem.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.