Science-advisor
REGISTER info/FAQ
Login
username
password
     
forgot password?
register here
 
Research articles
  search articles
  reviews guidelines
  reviews
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
 
 
Stat
Members: 3643
Articles: 2'488'730
Articles rated: 2609

29 March 2024
 
  » arxiv » 1710.9955

 Article overview


Strong Ramsey Games in Unbounded Time
Stefan David ; Ivailo Hartarsky ; Marius Tiba ;
Date 27 Oct 2017
AbstractFor 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   
 
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
important:
of broad interest:
readable:
new:
correct:
Global appreciation:

  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






ScienXe.org
» my Online CV
» Free


News, job offers and information for researchers and scientists:
home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2024 - Scimetrica