On the Computational Complexity and Strategies of Online Ramsey Theory

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F15%3A00238771" target="_blank" >RIV/68407700:21240/15:00238771 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.sciencedirect.com/science/article/pii/S1571065315001456" target="_blank" >http://www.sciencedirect.com/science/article/pii/S1571065315001456</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.endm.2015.06.099" target="_blank" >10.1016/j.endm.2015.06.099</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On the Computational Complexity and Strategies of Online Ramsey Theory

Popis výsledku v původním jazyce

An online Ramsey game $(G,H)$ is a game between Builder and Painter, alternating in turns. In each round Builder draws an edge and Painter colors it either red or blue. Builder wins if after some round there is a monochromatic copy of the graph $H$, otherwise Painter is the winner. The rule for Builder is that after each his move the resulting graph must belong to the class of graphs $G$. In this abstract we investigate the computational complexity of the related decision problem and we show that it isPSPACE-complete. Moreover, we study a generalization of online Ramsey game for hypergraphs and we provide a result showing that Builder wins the online Ramsey game for the case when $G$ and $H$ are $3$-uniform hyperforests and $H$ is $1$-degenerate.

Název v anglickém jazyce

On the Computational Complexity and Strategies of Online Ramsey Theory

Popis výsledku anglicky

An online Ramsey game $(G,H)$ is a game between Builder and Painter, alternating in turns. In each round Builder draws an edge and Painter colors it either red or blue. Builder wins if after some round there is a monochromatic copy of the graph $H$, otherwise Painter is the winner. The rule for Builder is that after each his move the resulting graph must belong to the class of graphs $G$. In this abstract we investigate the computational complexity of the related decision problem and we show that it isPSPACE-complete. Moreover, we study a generalization of online Ramsey game for hypergraphs and we provide a result showing that Builder wins the online Ramsey game for the case when $G$ and $H$ are $3$-uniform hyperforests and $H$ is $1$-degenerate.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

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 statě ve sborníku

Electronic Notes in Discrete Mathematics

ISBN

—

ISSN

1571-0653

e-ISSN

—

Počet stran výsledku

8

Strana od-do

729-736

Název nakladatele

Elsevier Science Publishers B.V.

Místo vydání

Amsterdam

Místo konání akce

Bergen

Datum konání akce

31. 8. 2015

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—