Mathematical Researches
پژوهش های ریاضی
mmr
Basic Sciences
http://mmr.khu.ac.ir
1
admin
2588-2546
2588-2554
10.61186/mmr
fa
jalali
1400
9
1
gregorian
2021
12
1
7
3
online
1
fulltext
fa
عدد رمزی یالی چند رنگی مسیرها
Multicolor Size-Ramsey Number of Paths
جبر
alg
علمی پژوهشی بنیادی
S
<div></div>
<div>گراف $ F $ که با نماد<br>
$ hat{r}(F,r) $ </div>
<div>نشان داده میشود، برابر است با کوچکترین عدد صحیح $ m $ بهطوری که یک گراف $ G $ با $ m $ یال وجود داشته باشد که در هر رنگآمیزی از یالهای گراف $ G $ با $ r $ رنگ، یک کپی تک رنگ از گراف $ F $ وجود داشته باشد. </div>
<div>کریولویچ و بهطور جداگانه دودک و پرالات برای مسیرهای $ P_n $ نشان دادهاند که برای $ n $ به اندازه کافی بزرگ، </div>
<div>$ hat{r}(P_n, r) leq 600 r^2(ln r) n$.</div>
<div>در این مقاله ما با اثباتی کاملا متفاوت این کران را بهبود داده و ثابت میکنیم</div>
<div>$ hat{r}(P_n, r) leq 18(1+o_r(1)) r^2(ln r) n$.</div>
<div>لازم به تذکر است که کران بالای بهدست آمده تقریباً بهینه است، زیرا </div>
<div>میدانیم که </div>
<div>$ hat{r}(P_n, r) = Omega(r^2n) $.</div>
The size-Ramsey number of a graph <img alt="" height="17" src="file:///C:UsersUser1AppDataLocalTempmsohtmlclip1�1clip_image002.png" width="7" > denoted by is the smallest integer <img alt="" height="17" src="file:///C:UsersUser1AppDataLocalTempmsohtmlclip1�1clip_image006.png" width="11" > such that there is a graph with <img alt="" height="17" src="file:///C:UsersUser1AppDataLocalTempmsohtmlclip1�1clip_image006.png" width="11" > edges with this property that for any coloring of the edges of <img alt="" height="17" src="file:///C:UsersUser1AppDataLocalTempmsohtmlclip1�1clip_image010.png" width="9" > with<img alt="" height="17" src="file:///C:UsersUser1AppDataLocalTempmsohtmlclip1�1clip_image012.png" width="10" > colors, <img alt="" height="17" src="file:///C:UsersUser1AppDataLocalTempmsohtmlclip1�1clip_image010.png" width="9" > contains a monochromatic copy of<img alt="" height="17" src="file:///C:UsersUser1AppDataLocalTempmsohtmlclip1�1clip_image014.png" width="12" >. 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.<br>
Addressing a question posed by Erdős‚ Beck [2] proved that the size-Ramsey number of the path <img alt="" height="17" src="file:///C:UsersUser1AppDataLocalTempmsohtmlclip1�1clip_image016.png" width="12" > is linear in <img alt="" height="17" src="file:///C:UsersUser1AppDataLocalTempmsohtmlclip1�1clip_image018.png" width="8" > 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].<br>
<a href="./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">./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</a>
عدد رمزی, عدد رمزی یالی, مسیر
Ramsey number, Size Ramsey number, path
485
494
http://mmr.khu.ac.ir/browse.php?a_code=A-10-867-1&slc_lang=fa&sid=1
Ramin
Javadi
رامین
جوادی
rjavadi@cc.iut.ac.ir
10031947532846005095
10031947532846005095
Yes
Isfahan University of Technology
دانشگاه صنعتی اصفهان
Meysam
Miralaei
میثم
میرعلایی
m.miralaei@math.iut.ac.ir
10031947532846005096
10031947532846005096
No
Isfahan University of Technology
دانشگاه صنعتی اصفهان