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

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F19%3A00499813" target="_blank" >RIV/67985840:_____/19:00499813 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1137/18M117488X" target="_blank" >http://dx.doi.org/10.1137/18M117488X</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/18M117488X" target="_blank" >10.1137/18M117488X</a>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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's 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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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's 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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

SIAM Journal on Discrete Mathematics

ISSN

0895-4801

e-ISSN

—

Svazek periodika

33

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

27

Strana od-do

68-94

Kód UT WoS článku

000462584900003

EID výsledku v databázi Scopus

2-s2.0-85064244502