×

An upper bound for the restricted online Ramsey number. (English) Zbl 1416.05190

Summary: The restricted \((m, n; N)\)-online Ramsey game is a game played between two players, Builder and Painter. The game starts with \(N\) isolated vertices. Each turn Builder picks an edge to build and Painter chooses whether that edge is red or blue, and Builder aims to create a red \(K_m\) or blue \(K_n\) in as few turns as possible. The restricted online Ramsey number \(\widetilde{r}(m, n; N)\) is the minimum number of turns that Builder needs to guarantee her win in the restricted \((m, n; N)\)-online Ramsey game. We show that if \(N = r(n, n)\), \[\widetilde{r}(n, n; N) \leq (\substack{N \\ 2}) - \Omega(N \log N),\] motivated by a question posed by D. Conlon et al. [“Online Ramsey numbers and the subgraph query problem”, Preprint, arXiv:1806.09726]. The equivalent game played on infinitely many vertices is called the online Ramsey game. As almost all known Builder strategies in the online Ramsey game end up reducing to the restricted setting, we expect further progress on the restricted online Ramsey game to have applications in the general case.

MSC:

05C57 Games on graphs (graph-theoretic aspects)
91A43 Games involving graphs
05D10 Ramsey theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Beck, J., Achievement games and the probabilistic method, Combinatorics, Paul Erdős is Eighty, 1, 51-78 (1993) · Zbl 0806.90146
[2] Conlon, D., On-line Ramsey numbers, SIAM J. Discrete Math., 23, 1954-1963 (2009) · Zbl 1213.05177
[3] Conlon, D.; Fox, J.; Grinshpun, A.; He, X., Online Ramsey numbers and the subgraph query problem (2018), preprint arXiv:1806.09726
[4] Erdős, P., Some remarks on the theory of graphs, Bull. Amer. Math. Soc., 53, 292-294 (1947) · Zbl 0032.19203
[5] Erdős, P.; Szekeres, G., A combinatorial problem in geometry, Compos. Math., 2, 463-470 (1935) · JFM 61.0651.04
[6] Erdős, P.; Szemerédi, E., On a Ramsey type theorem, Period. Math. Hungar., 2, 295-299 (1972) · Zbl 0242.05122
[7] Kóvari, T.; Sós, V.; Turán, P., On a problem of K. Zarankiewicz, Colloq. Math., 3, 50-57 (1954) · Zbl 0055.00704
[8] Kurek, A.; Ruciński, A., Two variants of the size Ramsey number, Discuss. Math. Graph Theory, 25, 141-149 (2005) · Zbl 1074.05062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.