| | |
| | |
Stat |
Members: 3643 Articles: 2'488'730 Articles rated: 2609
29 March 2024 |
|
| | | |
|
Article overview
| |
|
Strong Ramsey Games in Unbounded Time | Stefan David
; Ivailo Hartarsky
; Marius Tiba
; | Date: |
27 Oct 2017 | Abstract: | For two graphs $B$ and $H$ the strong Ramsey game $mathcal{R}(B,H)$ on the
board $B$ and with target $H$ is played as follows. Two players alternately
claim edges of $B$. The first player to build a copy of $H$ wins. If none of
the players win, the game is declared a draw. A notorious open question of Beck
asks whether the first player has a winning strategy in $mathcal{R}(K_n,K_k)$
in bounded time as $n
ightarrowinfty$. Surprisingly, Hefetz et al.
constructed a $5$-uniform hypergraph $mathcal{H}$, for which they prove that
the first player does not have a winning strategy in
$mathcal{R}(K_n^{(5)},mathcal{H})$ in bounded time. They naturally ask
whether the same result holds for graphs. In this paper we make further
progress in decreasing the rank.
In our first main result, we construct a graph $G$ (in fact $G=K_6setminus
K_4$) and prove that the first player does not have a winning strategy in
$mathcal{R}(K_n sqcup K_n,G)$ in bounded time. As an application of this
result we deduce our second main result in which we construct the $4$-uniform
hypergraph $G’$ and prove that the first player does not have a winning
strategy in $mathcal{R}(K_n^{(4)},G’)$ in bounded time. This improves the
result in the paper above.
An equivalent formulation of our first result is that the game
$mathcal{R}(K_omegasqcup K_omega,G)$ is a draw. Another reason for interest
in the board $K_omegasqcup K_omega$ is a folklore result that the disjoint
union of two finite positional games both of which are first player wins is
also a first player win. An amusing corollary of our first result is that at
least one of the following two natural statements is false: (1) for every graph
$H$, $mathcal{R}(K_omega,H)$ is a first player win; (2) for every graph $H$
if $mathcal{R}(K_omega,H)$ is a first player win, then
$mathcal{R}(K_omegasqcup K_omega,H)$ is also a first player win. | Source: | arXiv, 1710.9955 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |