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

Abstract

div/div divگراف $ F $ که با نمادbr $ hat{r}(F,r) $nbsp;/div

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

divکریولویچ و ‌‌‌به‌طور جداگانه دودک و پرالات برای مسیرهای $ P_n $ نشان داده‌اند که برای $ n $nbsp; به‌ اندازه کافی بزرگ،nbsp;/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لازم به تذکر است که کران بالای به‌دست آمده تقریباً بهینه است، زیراnbsp;/div

divمی‌دانیم کهnbsp;/div

div$ hat{r}(P_n, r) = Omega(r^2n) $./div