The asymptotic of off-diagonal online Ramsey numbers for paths. (English) Zbl 07920241
Summary: We prove that for every \(k \geq 10\), the online Ramsey number for paths \(P_k\) and \(P_n\) satisfies \(\tilde{r} (P_k, P_n) \geq \frac{5}{3}n + \frac{k}{9} - 4\), matching up to a linear term in \(k\) the upper bound recently obtained by M. Bednarska-Bzdȩga [Eur. J. Comb. 118, Article ID 103873, 16 p. (2024; Zbl 1535.05192)]. In particular, this implies \(\lim_{n \to \infty} \frac{\tilde{r} (P_k, P_n)}{n} = \frac{5}{3}\), whenever \(10 \leq k = o(n)\), disproving a conjecture by J. Cyman et al. [Electron. J. Comb. 22, No. 1, Research Paper P1.15, 32 p. (2015; Zbl 1305.05138)].
MSC:
| 05C55 | Generalized Ramsey theory |
| 05D10 | Ramsey theory |
| 05C38 | Paths and cycles |
| 05C57 | Games on graphs (graph-theoretic aspects) |
| 91A43 | Games involving graphs |
| 91A46 | Combinatorial games |
References:
| [1] | Adamski, Grzegorz; Bednarska-Bzdęga, Małgorzata, Online size Ramsey numbers: Odd cycles vs connected graphs, 2021, arXiv preprint arXiv:2111.14147 |
| [2] | Adamski, Grzegorz; Bednarska-Bzdęga, Małgorzata, Online size Ramsey numbers: Path vs \(C \text{\_} 4\), 2022, arXiv preprint arXiv:2211.12204 |
| [3] | Adamski, Grzegorz; Bednarska-Bzdęga, Małgorzata; Blažej, Václav, Online Ramsey numbers: Long versus short cycles, 2023, arXiv preprint arXiv:2303.15194 |
| [4] | Balogh, József; Clemen, Felix Christian; Heath, Emily; Lavrov, Mikhail, A strengthening of the erdős-Szekeres theorem, European J. Combin., 101, Article 103456 pp., 2022 · Zbl 1486.05303 |
| [5] | Beck, József, On size Ramsey number of paths, trees, and circuits I, J. Graph Theory, 7, 1, 115-129, 1983 · Zbl 0508.05047 |
| [6] | Beck, József, Achievement games and the probabilistic method, Combinatorics, 1, 51-78, 1993, Paul Erdős is Eighty · Zbl 0806.90146 |
| [7] | Bednarska-Bzdęga, Małgorzata, Off-diagonal online size Ramsey numbers for paths, European J. Combin., 118, Article 103873 pp., 2024 · Zbl 1535.05192 |
| [8] | Václav Blažej, Pavel Dvořák, Tomáš Valla, On induced online Ramsey number of paths, cycles, and trees, in: Computer Science-Theory and Applications: 14th International Computer Science Symposium in Russia, CSR 2019, Novosibirsk, Russia, July 1-5, 2019, Proceedings 14, 2019, pp. 60-69. · Zbl 1535.05193 |
| [9] | Cyman, Joanna; Dzido, Tomasz; Lapinskas, John; Lo, Allan, On-line Ramsey numbers of paths and cycles, Electron. J. Combin., 1-15, 2015 · Zbl 1305.05138 |
| [10] | Grytczuk, Jarosław A.; Kierstead, Hal A.; Prałat, Paweł, On-line Ramsey numbers for paths and stars, Discrete Math. Theor. Comput. Sci., 10, 3, 63-74, 2008 · Zbl 1196.05053 |
| [11] | Kurek, Andrzej; Ruciński, Andrzej, Two variants of the size Ramsey number, Discuss. Math. Graph Theory, 25, 1-2, 141-149, 2005 · Zbl 1074.05062 |
| [12] | Pérez-Giménez, Xavier; Prałat, Paweł; West, Douglas B., On-line size Ramsey number for monotone k-uniform ordered paths with uniform looseness, European J. Combin., 92, Article 103242 pp., 2021 · Zbl 1458.05164 |
| [13] | Pralat, Pawel, A note on small on-line Ramsey numbers for paths and their generalization, Australas. J. Combin., 40, 27, 2008 · Zbl 1141.05061 |
| [14] | Prłaat, Pawel, A note on off-diagonal small on-line Ramsey numbers for paths, Ars Combin., 107, 295-306, 2012 · Zbl 1289.05333 |
| [15] | Zhang, Yanbo; Zhang, Yixin, Proof of a conjecture on online Ramsey numbers of paths, 2023, arXiv preprint arXiv:2302.13640 |
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.
