On the Computational Complexity and Strategies of Online Ramsey Theory

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
On the Computational Complexity and Strategies of Online Ramsey Theory
Original language description
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.
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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

Similar results(10)