حدس $[1]$: به ازای هر $c$ و $k$،$f_1$ وجود دارد که برای هر $n> f_1(c,k)$ اگر یال‌های $k_n$ را با $c\times n$ رنگ کنیم و رنگ‌آمیزی معتبر باشد، آن‌گاه مسیری به طول $k$ یال وجود دارد که هر یال مسیر(به جز دو یال اول) با دو یال قبلی‌اش هم‌رنگ باشد.

حدس $[2]$: به ازای هر $c$ و $k$،$f_2$ وجود دارد که برای هر $n> f_2(c,k)$ اگر یال‌های $k_{n,n}$ را با $c\times n$ رنگ کنیم و رنگ‌آمیزی معتبر باشد، آن‌گاه مسیری به طول $k$ یال وجود دارد که هر یال مسیر(به جز دو یال اول) با دو یال قبلی‌اش هم‌رنگ باشد.

حدس $[3]$: به ازای هر $c$ و $k$،$f_3$ وجود دارد که برای هر $n> f_3(c,k)$ اگر یال‌های $k_{n,n}$ را با $c\times n$ رنگ کنیم و رنگ‌آمیزی معتبر باشد و اجتماع هر دو رنگ دور نداشته باشد، آن‌گاه مسیری به طول $k$ یال وجود دارد که هر یال مسیر(به جز دو یال اول) با دو یال قبلی‌اش هم‌رنگ باشد.

قضیه‌$[4]$: هر مجموعه‌ی $A=\{a_1,…,a_n\} \subset N$ که $a_i < c \times n$ و $n>f_4(c,k)$، شامل تصاعدی حسابی به طول $k$ است.

۱ ) فرض کنید $L$ به راس‌های گراف $k_{2m}$، اعضای متمایز $\{0,1\}^m$ را نسبت می‌دهد( مثلا $(L(v)=(Lv_1,…Lv_m)$. به یال $vu$ از $k_{2m}$ رنگ $$((Lv_1+Lu_1)(mod 2),…,(Lv_m+Lu_m)(mod 2))$$

را نسبت می‌دهیم. ثابت کنید مولفه‌های حاصل از یال‌های $t$ رنگ خاص حداکثر $2^t$ راس دارند.

۲ ) برای هر $k>4$ و $f_1$ دلخواه، مثال نقضی برای حدس$[1]$ و حدس $[2]$ ارائه دهید.

۳ ) با استفاده از حدس $[3]$، $f_4$ای پیدا کنید و قضیه‌ی $[4]$ را اثبات کنید.

• سوال بعد
• سوال قبل