Multicolor Size-Ramsey Number of Paths

Authors
Ramin Javadi
Meysam Miralaei
Isfahan University of Technology
10.52547/mmr.7.3.485
Abstract
The size-Ramsey number of a graph denoted by is the smallest integer such that there is a graph with edges with this property that for any coloring of the edges of with colors, contains a monochromatic copy of. The investigation of the size-Ramsey numbers of graphs was initiated by Erdős‚ Faudree‚ Rousseau and Schelp in 1978. Since then, Size-Ramsey numbers have been studied with particular focus on the case of trees and bounded degree graphs.

Addressing a question posed by Erdős‚ Beck [2] proved that the size-Ramsey number of the path is linear in by means of a probabilistic construction. In fact, Beck’s proof implies that and this upper bound was improved several times. Currently‚ the best known upper bound is due to Dudek and Prałat [4] which proved that . On the other hand‚ the first nontrivial lower bound for was provided by Beck and his result was subsequently improved by Dudek and Prałat [3] who showed that. The strongest known lower bound was proved recently by Bal and DeBiasio [1].

./files/site1/files/%D8%AC%D9%88%D8%A7%D8%AF%DB%8C_%D9%85%DB%8C%D8%B1%D8%B9%D9%84%D8%A7%DB%8C%DB%8C.pdf
Keywords
Ramsey number
Size Ramsey number
path
[1] J. Beck, On size Ramsey number of paths, trees, and circuits. I, J. Graph Theory 7 (1983), no. 1, 115–129.

[2] J. Beck , On size Ramsey number of paths, trees and circuits. II, Mathematics of Ramsey theory, Algorithms Combin. , vol. 5, Springer, Berlin, 1990, pp. 34–45.

[3] B. Bollobás, Extremal graph theory with emphasis on probabilistic methods, CBMS Regional Conference Series in Mathematics, vol. 62, Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1986.

[4] B. Bollobás, Random graphs, second ed., Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001.

[5] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Vol. 290. Macmillan London, 2008.

[6] A. Dudek and P. Prałat, An alternative proof of the linearity of the size-Ramsey number of paths, Combin. Probab. Comput. 24 (2015), no. 3, 551–555.

[7] A. Dudek and P. Prałat, On some multicolor Ramsey properties of random graphs, SIAM J. Discrete Math. 31 (2017), no. 3, 2079–2092.

[8] A. Dudek and P. Prałat, Note on the multicolor size-Ramsey number for paths. Electron. J. Combin. 25 (2018), no. 3, Paper 3.35, 5 pp.

[9] P. Erdős, On an extremal problem in graph theory, Colloq. Math. 13 (1964/1965), 251–254.

[10] P. Erdős, On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), no. 1, 25–42.

[11] P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp, The size Ramsey number, Period. Math. Hungar. 9 (1978), no. 1-2, 145–161.

[12] M. Mitzenmacher and E. Upfal, Probability and computing: Randomized algorithms and probabilistic analysis, Cambridge University Press, Cambridge, 2005.

[13] S. Janson, T. łuczak, and A. Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000.

[14] M. Krivelevich, Long cycles in locally expanding graphs, with applications, to appear in Combinatorica.

[15] S. Letzter, Path Ramsey number for random graphs, Combin. Probab. Comput. 25 (2016), no. 4, 612–622.

[16] L. Pósa, Hamiltonian circuits in random graphs. Discrete Math. 14 (1976), no. 4, 359–364.

[17] C. You and Q. Lin, Size Ramsey numbers of paths, ArXiv e-peints, (2018).
Mathematical Research
Volume 7, Issue 3 - Serial Number 18
Autumn 2021
Pages 485-494