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

DOI10.1137/18M117488XMaRDI QIDQ4646256zbMATH OpenOpenAlexWikidataFDO

Authors Robert Hancock

Publication date 11 January 2019

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

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)

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.

Recommendations

• On the threshold for the maker-breaker \(H\)-game
• Random-player maker-breaker games
• Positional games on random graphs
• A threshold for the maker-breaker clique game
• Maker-Breaker games on randomly perturbed graphs

Cites work

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

Cited in

(6)

• scientific article; zbMATH DE number 7069683 (Why is no real title available?)
• Maker-breaker resolving game
• Maker–Breaker percolation games I: crossing grids
• Maker-breaker percolation games. II: Escaping to infinity
• Maker-breaker Rado games for equations with radicals
• An asymmetric random Rado theorem for single equations: The 0‐statement

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)