The Maker--Breaker Rado Game on a Random Set of Integers

DOI10.1137/18M117488XzbMATH Open1419.91116arXiv1803.03793OpenAlexW2963928044WikidataQ128607577 ScholiaQ128607577MaRDI QIDQ4646256FDOQ4646256

Robert Hancock

Publication date: 11 January 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Given an integer-valued matrix $A$ of dimension $ellimesk$ 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.

Full work available at URL: https://arxiv.org/abs/1803.03793

zbMATH Keywords

games on graphsRado's theoremMaker-Breaker games

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Positional games
• Extremal results for random discrete structures
• Combinatorial theorems in sparse random sets
• Hypergraph containers
• Independent sets in hypergraphs
• Combinatorial Games
• On a combinatorial game
• Biased positional games for which random strategies are nearly optimal
• On the threshold for the maker-breaker \(H\)-game
• Positional games on random graphs
• Threshold functions
• A removal lemma for systems of linear equations over finite fields
• Rado Partition Theorem for Random Subsets of Integers
• Threshold Functions for Ramsey Properties
• Studien zur Kombinatorik
• Ramsey properties of random discrete structures
• Random graphs with monochromatic triangles in every edge coloring
• Van der Waerden and Ramsey type games
• On the optimality of the uniform random strategy
• Independent Sets in Hypergraphs and Ramsey Properties of Graphs and the Integers
• A note on sparse supersaturation and extremal results for linear homogeneous systems

Cited In (6)

• Maker-breaker percolation games. II: Escaping to infinity
• An asymmetric random Rado theorem for single equations: The 0‐statement
• Maker-breaker resolving game
• Maker–Breaker percolation games I: crossing grids
• Maker-breaker Rado games for equations with radicals
• Title not available (Why is that?)

This page was built for publication: The Maker--Breaker Rado Game on a Random Set of Integers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4646256)