On Induced Online Ramsey Number of Paths, Cycles, and Trees
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10404271" target="_blank" >RIV/00216208:11320/19:10404271 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.1007/978-3-030-19955-5_6" target="_blank" >https://doi.org/10.1007/978-3-030-19955-5_6</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-030-19955-5_6" target="_blank" >10.1007/978-3-030-19955-5_6</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On Induced Online Ramsey Number of Paths, Cycles, and Trees
Popis výsledku v původním jazyce
An online Ramsey game is a game between Builder and Painter, alternating in turns. They are given a fixed graph H and a an infinite set of independent vertices G. In each round Builder draws a new edge in G and Painter colors it either red or blue. Builder wins if after some finite round there is a monochromatic copy of the graph H, otherwise Painter wins. The online Ramsey number (r) over tilde (H) is the minimum number of rounds such that Builder can force a monochromatic copy of H in G. This is an analogy to the size-Ramsey number (r) over bar (H) defined as the minimum number such that there exists graph G with (r) over bar (H) edges where for any edge two-coloring G contains a monochromatic copy of H. In this extended abstract, we introduce the concept of induced online Ramsey numbers: the induced online Ramsey number (r) over tilde (ind)(H) is the minimum number of rounds Builder can force an induced monochromatic copy of H in G. We prove asymptotically tight bounds on the induced online Ramsey numbers of paths, cycles and two families of trees. Moreover, we provide a result analogous to Conlon [On-line Ramsey Numbers, SIAM J. Discr. Math. 2009], showing that there is an infinite family of trees T-1, T-2,..., vertical bar T-i vertical bar < vertical bar Ti+1 vertical bar for i >= 1, such that (i ->infinity)lim <(r)over tilde>(T-i)/(r) over bar (T-i) = 0.
Název v anglickém jazyce
On Induced Online Ramsey Number of Paths, Cycles, and Trees
Popis výsledku anglicky
An online Ramsey game is a game between Builder and Painter, alternating in turns. They are given a fixed graph H and a an infinite set of independent vertices G. In each round Builder draws a new edge in G and Painter colors it either red or blue. Builder wins if after some finite round there is a monochromatic copy of the graph H, otherwise Painter wins. The online Ramsey number (r) over tilde (H) is the minimum number of rounds such that Builder can force a monochromatic copy of H in G. This is an analogy to the size-Ramsey number (r) over bar (H) defined as the minimum number such that there exists graph G with (r) over bar (H) edges where for any edge two-coloring G contains a monochromatic copy of H. In this extended abstract, we introduce the concept of induced online Ramsey numbers: the induced online Ramsey number (r) over tilde (ind)(H) is the minimum number of rounds Builder can force an induced monochromatic copy of H in G. We prove asymptotically tight bounds on the induced online Ramsey numbers of paths, cycles and two families of trees. Moreover, we provide a result analogous to Conlon [On-line Ramsey Numbers, SIAM J. Discr. Math. 2009], showing that there is an infinite family of trees T-1, T-2,..., vertical bar T-i vertical bar < vertical bar Ti+1 vertical bar for i >= 1, such that (i ->infinity)lim <(r)over tilde>(T-i)/(r) over bar (T-i) = 0.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
—
Návaznosti
S - Specificky vyzkum na vysokych skolach
Ostatní
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ů
Údaje specifické pro druh výsledku
Název statě ve sborníku
COMPUTER SCIENCE - THEORY AND APPLICATIONS
ISBN
978-3-030-19955-5
ISSN
0302-9743
e-ISSN
1611-3349
Počet stran výsledku
10
Strana od-do
60-69
Název nakladatele
SPRINGER INTERNATIONAL PUBLISHING AG
Místo vydání
CHAM
Místo konání akce
Novosibirsk
Datum konání akce
1. 7. 2019
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
000490894900006