Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2409.01917 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909303379591168 |
|---|---|
| author | Heath, Emily King, Dylan McCourt, Grace Sheats, Hannah Wisby, Justin |
| author_facet | Heath, Emily King, Dylan McCourt, Grace Sheats, Hannah Wisby, Justin |
| contents | The online ordered Ramsey game is played between two players, Builder and Painter, on an infinite sequence of vertices with ordered graphs $(G_1,G_2)$, which have linear orderings on their vertices. On each turn, Builder first selects an edge before Painter colors it red or blue. Builder's objective is to construct either an ordered red copy of $G_1$ or an ordered blue copy of $G_2$, while Painter's objective is to delay this for as many turns as possible. The online ordered Ramsey number $r_o(G_1,G_2)$ is the number of turns Builder takes to win in the case that both players play optimally.
Few lower bounds are known for this quantity. In this paper, we introduce a succinct proof of a new lower bound based on the maximum left- and right-degrees in the ordered graphs. We also upper bound $r_o(G_1,G_2)$ in two cases: when $G_1$ is a cycle and $G_2$ a complete bipartite graph, and when $G_1$ is a tree and $G_2$ a clique. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_01917 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Online Ramsey numbers of ordered graphs Heath, Emily King, Dylan McCourt, Grace Sheats, Hannah Wisby, Justin Combinatorics 05D10 The online ordered Ramsey game is played between two players, Builder and Painter, on an infinite sequence of vertices with ordered graphs $(G_1,G_2)$, which have linear orderings on their vertices. On each turn, Builder first selects an edge before Painter colors it red or blue. Builder's objective is to construct either an ordered red copy of $G_1$ or an ordered blue copy of $G_2$, while Painter's objective is to delay this for as many turns as possible. The online ordered Ramsey number $r_o(G_1,G_2)$ is the number of turns Builder takes to win in the case that both players play optimally. Few lower bounds are known for this quantity. In this paper, we introduce a succinct proof of a new lower bound based on the maximum left- and right-degrees in the ordered graphs. We also upper bound $r_o(G_1,G_2)$ in two cases: when $G_1$ is a cycle and $G_2$ a complete bipartite graph, and when $G_1$ is a tree and $G_2$ a clique. |
| title | Online Ramsey numbers of ordered graphs |
| topic | Combinatorics 05D10 |
| url | https://arxiv.org/abs/2409.01917 |