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

عدد رمزی اندازهای 𝑟 رنگی گراف f که با نماد (𝐹‚𝑟) نشان داده می شود، کوچکترین عدد صحیح m تعریف می شود به طوری که یک گراف g با m یال وجود داشته باشد که در هر رنگ آمیزی از یال های گراف g با r رنگ، یک کپی تکرنگ از گراف وجود داشته باشد. کریولویچ و به طور جداگانه، دودک و پرالات برای مسیر 𝑃𝑛 نشان داده اند که برای n به اندازۀ کافی بزرگ، ̂(𝑃𝑛 ‚ 𝑟)≤604𝑟^2ln𝑟𝑛 در این مقاله با اثباتی کام بالا متفاوت این کران بالا را بهبود داده و ثابت میکنیم (𝑃𝑛 ‚ 𝑟)≤ 18(1+𝑜𝑟(1))𝑟^2ln𝑟 𝑛 لازم به ذکر است که کران بالای به دست آمده تقریبا بهینه است

multicolor size ramsey number of paths

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