A Note on On-Line Ramsey Numbers of Stars and Paths
Tóm tắt
An on-line Ramsey game is a game between two players, Builder and Painter, on an initially empty graph with unbounded set of vertices. In each round, Builder selects two vertices and joins them with an edge while Painter colours the edge immediately with either red or blue. Builder’s aim is to force either a red copy of a fixed graph G or a blue copy of a fixed graph H. The game ends with Builder’s victory when Builder manages to force either a red G or a blue H. The minimum number of rounds for Builder to win the game, regardless of Painter’s strategy, is the on-line Ramsey number
$${\tilde{r}}(G,H)$$
. This note focuses on the case when G and H are stars and paths. In particular, we will prove the upper bound of
$${\tilde{r}}(S_3,P_{l+1})\le 5l/3+2$$
. We will also present an alternative proof for the upper bound of
$${\tilde{r}}(S_2 = P_3, P_{l+1}) = \lceil 5l/4\rceil $$
.
Tài liệu tham khảo
Beck, J.: Achievement games and the probabilistic method. Combin. Paul Erdős is Eighty Bolyai Soci. Math. Stud. 1, 51–78 (1993)
Butterfield, J., Grauman, T., Kinnersley, W.B., Milans, K.G., Stocker, C., West, D.B.: On-line Ramsey theory for bounded degree graphs. Electron. J. Combin. 18(11), 136 (2011)
Conlon, D.: A new upper bound for diagonal Ramsey numbers. Ann. Math. 170, 941–960 (2009)
Conlon, D.: On-line Ramsey numbers. SIAM J. Discrete Math. 23(4), 1953–1954 (2009)
Cyman, J., Dzido, T., Lapinskas, J., Lo, A.: On-line Ramsey numbers of paths and cycles. Electron. J. Combin. 22, 1–15 (2015)
Erdős, P., Faudree, R.J., Rousseau, C.C., Schelp, R.H.: The size Ramsey number. Period. Math. Hung. 9, 145–161 (1978)
Friedgut, E., Kohayakawa, Y., Rödl, V., Ruciński, A., Tetali, P.: Ramsey games against a one-armed bandit. Combin. Prob. Comput. 12, 515–545 (2003)
Grytczuk, J., Hałuszczak, M., Kierstead, H.: On-line Ramsey theory. Electron. J. Combin. 11(1), 57 (2004)
Grytczuk, J., Kierstead, H., Prałat, P.: On-line Ramsey numbers for paths and stars. Discrete Math. Theor. Comput. Sci. 10(3), 63–74 (2008)
Kurek, A., Ruciński, A.: Two variants of the size Ramsey number. Discuss. Math. Graph Theory 25, 141–149 (2005)
Prałat, P.: A note on off-diagonal small on-line Ramsey numbers for paths. ARS Combin. 107, 295–306 (2012)
Prałat, P.: A note on small on-line Ramsey numbers for paths and their generalisations. Austr. J. Combin. 40, 27–36 (2008)
Prałat, P.: \({\tilde{r}}(3,4)=17 \). Electric J. Combin. 15, 67 (2008)
Ramsey, F.: On a problem of formal logic. Proc. Lond. Math. Soc. 30, 264–286 (1930)
Spencer, J.: Ramsey’s theorem: a new lower bound. J. Combin. Theory Ser. A 18, 108–115 (1975)