عدد رمزی یالی چند رنگی مسیرها

نویسندگان
رامین جوادی
میثم میرعلایی
دانشگاه صنعتی اصفهان
10.52547/mmr.7.3.485
چکیده
گراف $ F $ که با نماد

$ hat{r}(F,r) $

نشان داده می‌شود، برابر است با کوچکترین عدد صحیح $ m $ به‌طوری ‌که یک گراف $ G $ با $ m $ یال وجود داشته باشد که در هر رنگ‌آمیزی از یال‌های گراف $ G $ با $ r $ رنگ، یک کپی تک رنگ از گراف $ F $ وجود داشته باشد.

کریولویچ و ‌‌‌به‌طور جداگانه دودک و پرالات برای مسیرهای $ P_n $ نشان داده‌اند که برای $ n $ به‌ اندازه کافی بزرگ،

$ hat{r}(P_n, r) leq 600 r^2(ln r) n$.

در این مقاله ما با اثباتی کاملا متفاوت این کران را بهبود داده و ثابت می‌کنیم

$ hat{r}(P_n, r) leq 18(1+o_r(1)) r^2(ln r) n$.

لازم به تذکر است که کران بالای به‌دست آمده تقریباً بهینه است، زیرا

می‌دانیم که

$ hat{r}(P_n, r) = Omega(r^2n) $.
کلیدواژه‌ها
عدد رمزی
عدد رمزی یالی
مسیر

عنوان مقاله English

Multicolor Size-Ramsey Number of Paths

نویسندگان English

Ramin Javadi
Meysam Miralaei
Isfahan University of Technology
چکیده English

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

کلیدواژه‌ها English

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).