×

Online size Ramsey numbers: odd cycles vs connected graphs. (English) Zbl 07921990

Summary: Given two graph families \(\mathcal H_1\) and \(\mathcal H_2\), a size Ramsey game is played on the edge set of \(K_\mathbb{N}\). In every round, Builder selects an edge and Painter colours it red or blue. Builder is trying to force Painter to create a red copy of a graph from \(\mathcal H_1\) or a blue copy of a graph from \(\mathcal H_2\) as soon as possible. The online (size) Ramsey number \(\tilde{r}(\mathcal H_1,\mathcal H_2)\) is the smallest number of rounds in the game provided Builder and Painter play optimally. We prove that if \(\mathcal H_1\) is the family of all odd cycles and \(\mathcal H_2\) is the family of all connected graphs on \(n\) vertices and \(m\) edges, then \(\tilde{r}(\mathcal H_1,\mathcal H_2)\geqslant \varphi n + m-2\varphi+1\), where \(\varphi\) is the golden ratio, and for \(n\geqslant 3, m\le (n-1)^2/4\) we have \(\tilde{r}(\mathcal H_1,\mathcal H_2)\leqslant n+2m+O(\sqrt{m-n+1})\). We also show that \(\tilde{r}(C_3,P_n)\leqslant 3n-4\) for \(n\geqslant 3\). As a consequence we get \(2.6n-3\leqslant \tilde{r}(C_3,P_n)\leqslant 3n-4\) for every \(n\geqslant 3\).

MSC:

05C57 Games on graphs (graph-theoretic aspects)
91A43 Games involving graphs
91A46 Combinatorial games
05C75 Structural characterization of families of graphs
05C55 Generalized Ramsey theory
05D10 Ramsey theory

Keywords:

Ramsey game

References:

[1] D. Bal, E. Schudrich, On the size Ramsey number of all cycles versus a path, Discrete Math. 344 (2021), no. 112322, arXiv:2005.08075. · Zbl 1460.05123
[2] J. Beck, Achievement games and the probabilistic method, Combinatorics, Paul Erdős is Eighty, Vol. 1, Bolyai Soc. Math. Studies (1993), 51-78. · Zbl 0806.90146
[3] V. Blažej, P. Dvořák, T. Valla, On induced online Ramsey number of paths, cycles, and trees, The 14th International Computer Science Symposium in Russia, Lecture Notes in Computer Science. vol. 11532, Springer, 2019, 60-69, arXiv:1901.03671. · Zbl 1535.05193
[4] D. Conlon, On-line Ramsey numbers, SIAM Journal on Discrete Mathematics 23 (2009), 1954-1963, arXiv:0902.1715. · Zbl 1213.05177
[5] J. Cyman, T. Dzido, J. Lapinskas, A. Lo, On-line Ramsey numbers for paths and cycles, Electron. J. Comb. 22 (2015) #P1.15. doi:10.37236/4097. · Zbl 1305.05138 · doi:10.37236/4097
[6] A. Dudek, F. Khoeini, P. Pra󰀀 lat, Size-Ramsey numbers of cycles versus a path, Dis-crete Math. 341 (2018), 2095-2103, doi:10.1016/j.disc.2018.04.008. · Zbl 1387.05163 · doi:10.1016/j.disc.2018.04.008
[7] J. Dybizbański, T. Dzido, R. Zakrzewska, On-line Ramsey numbers for paths and short cycles, Discrete Appl. Math. 282 (2020), 265-270, doi:10.1016/j.dam.2020.03.004. · Zbl 1441.05156 · doi:10.1016/j.dam.2020.03.004
[8] P. Gordinowicz, P. Pra󰀀 lat, Small on-line Ramsey numbers -a new approach, Contrib. Discrete Math. 13 (2018), 101-111, doi:10.11575/cdm.v13i2.62731. · Zbl 1406.05108 · doi:10.11575/cdm.v13i2.62731
[9] J. Grytczuk, H. Kierstead, P. Pra󰀀 lat, On-line Ramsey numbers for paths and stars, Discrete Mathematics and Theoretical Computer Science 10 (2008), 63-74, doi:10.46298/dmtcs.427. · Zbl 1196.05053 · doi:10.46298/dmtcs.427
[10] A. Kurek, A. Ruciński, Two variants of the size Ramsey number, Discuss. Math. Graph Theory 25 (2005), 141-149, doi:10.7151/dmgt.1268. · Zbl 1074.05062 · doi:10.7151/dmgt.1268
[11] O. Pikhurko, Size Ramsey numbers of stars versus 3-chromatic graphs, Combi-natorica 21 (2001), 403-412, doi:10.1007/s004930100004, https://homepages. warwick.ac.uk/  maskat/Papers/StarK4.ps. · Zbl 0981.05073 · doi:10.1007/s004930100004
[12] E. Schudrich, Bipartite, size, and online Ramsey numbers of some cycles and paths, Master’s Thesis (2021), Montclair State University, https://digitalcommons. montclair.edu/cgi/viewcontent.cgi?article=1685&context=etd.
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.