پژوهش‌های ریاضی

گراف $ F $ که با نماد
$ hat{r}(F,r) $ 

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

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

$ hat{r}(P_n, r) leq ۶۰۰ r^۲(ln r) n$.

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

$ hat{r}(P_n, r) leq ۱۸(۱+o_r(۱)) r^۲(ln r) n$.

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

می‌دانیم که 

$ hat{r}(P_n, r) = Omega(r^۲n) $.