On the size Ramsey number of all cycles versus a path. (English) Zbl 1460.05123
Summary: We say \(G \to ( \mathcal{C} , P_n )\) if \(G - E ( F )\) contains an \(n\)-vertex path \(P_n\) for any spanning forest \(F \subset G\). The size Ramsey number \(\hat{R} ( \mathcal{C} , P_n )\) is the smallest integer \(m\) such that there exists a graph \(G\) with \(m\) edges for which \(G \to ( \mathcal{C} , P_n )\). A. Dudek et al. [ibid. 341, No. 7, 2095–2103 (2018; Zbl 1387.05163)] proved that for sufficiently large \(n\), \(2 . 0036 n \leq \hat{R} ( \mathcal{C} , P_n ) \leq 31 n\). In this note, we improve both the lower and upper bounds to \(2 . 066 n \leq \hat{R} ( \mathcal{C} , P_n ) \leq 5 . 25 n + O ( 1 )\). Our construction for the upper bound is completely different than the one considered by Dudek et al. [loc. cit.]. We also have a computer assisted proof of the upper bound \(\hat{R} ( \mathcal{C} , P_n ) \leq \frac{ 75}{ 19} n + O ( 1 ) < 3 . 947 n\).
Citations:
Zbl 1387.05163References:
| [1] | Bal, D.; DeBiasio, L., New lower bounds on the size-Ramsey number of a path (2019), arXiv preprint https://arxiv.org/abs/1909.06354 |
| [2] | Beck, J., On size Ramsey number of paths, trees and circuits. II, (Mathematics of Ramsey Theory (1990), Springer: Springer Berlin, Heidelberg), 34-45 · Zbl 0735.05056 |
| [3] | Bollobás, B., Extremal Graph Theory with Emphasis on Probabilistic Methods, Vol. 62 (1986), American Mathematical Soc. · Zbl 0597.05038 |
| [4] | Dudek, A.; Khoeini, F.; Prałat, P., Size-Ramsey numbers of cycles versus a path, Discrete Math., 341, 7, 2095-2103 (2018) · Zbl 1387.05163 |
| [5] | Dudek, A.; Prałat, P., An alternative proof of the linearity of the size-Ramsey number of paths, Combin. Probab. Comput., 24, 3, 551-555 (2015) · Zbl 1371.05172 |
| [6] | Dudek, A.; Prałat, P., On some multicolor Ramsey properties of random graphs, SIAM J. Discrete Math., 31, 3, 2079-2092 (2017) · Zbl 1370.05211 |
| [7] | Erdős, P., On the combinatorial problems which I would most like to see solved, Combinatorica, 1, 1, 25-42 (1981) · Zbl 0486.05001 |
| [8] | Haxell, P. E.; Kohayakawa, Y.; Łuczak, T., The induced size-Ramsey number of cycles, Combin. Probab. Comput., 4, 3, 217-239 (1995) · Zbl 0839.05073 |
| [9] | Javadi, R.; Khoeini, F.; Omidi, G. R.; Pokrovskiy, A., On the size-Ramsey number of cycles, Combin. Probab. Comput., 28, 6, 871-880 (2019) · Zbl 1436.05073 |
| [10] | Letzter, S., Path Ramsey number for random graphs, Combin. Probab. Comput., 25, 4, 612-622 (2016) · Zbl 1372.05228 |
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.
