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

گراف F که با نماد {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) .

* فرمول ها به درستی نمایش داده نمی شوند.