مبرهنة إيردوس-سيكريس

في الرياضيات، تنص مبرهنة إيردوس-سيكريس على أنه في كل متتالية مكونة من أعداد حقيقية بطول $rs+1$، يوجد لها متتالية جزئية متزايدة بطول $r+1$ أو متتالية جزئية متناقصة بطول $s+1$. هذه المبرهنة هي مبرهنة مثالية في نظرية رمزي، التي تبحث الانتظام وسط الفوضى.

تمت برهنة المبرهنة على يد بول إيردوس وجورج سيكريس في مقال لهما سنة 1935.

مثال

لـ r = 1 و s = 2، تخبرنا الصيغة بأنه لأي تبديل من 3 أعداد يوجد متتالية جزئية متزايدة بطون 3 أو متتالية جزئية متناقصة بطول 2. ننظر إلى جميع التبديلات من الأعداد 1,2,3:

• 1,2,3 متتالية جزئية متزايدة مكونة من كل الأعداد
• 1,3,2 يملك متتالية جزئية متناقصة 3,2
• 2,1,3 يملك متتالية جزئية متناقصة 2,1
• 2,3,1 يملك متتاليتين متناقصين 2,1 و 3,1
• 3,1,2 يملك متتاليتين متناقصين 3,1 و 3,2
• 3,2,1 متتالية جزئية متناقصة مكونة من كل الأعداد

برهان

يمكن برهنة مبرهنة إيردوس-سيكريس بالعديد من الطرق; steele (1995) عاين ستة براهين مختلفة لمبرهنة إيردوس-سيكريس، بما في ذلك البرهان التالي.

مبدأ برج الحمام

إذا كانت معطاه متتالية بطول rs + 1، نميز كل عدد n_i في المتتالية بالزوج (a_i,b_i)، بحيث أن a_i هو طول أطول متتالية متزايدة تنتهي بـ n_i و b_i هو طول أطول ممتالية متناقصة تنتهي بـ ,n_i. كل عددين في المتتالية مميزين بزوج مختلف:

• إذا كان i < j و n_i < n_j إذن a_i < a_j
• إذا كان i < j و n_i > n_j إذن b_i < b_j

ولكن هنالك rs علامة مميّزة بحيث أن a_i على الأكثر r و b_i على الأكثر s، ولذلك وفقا لمبدأ برج الحمام يجب أن تكون قيمة i بحيث a_i أو b_i خارج المجال. إذا كانت a_i خارج المجال إذن n_i هي جزء من متتالية متزايدة بطول 1 + r على الأقل، وإذا كانت b_i خارج المجال إذن n_i هي جزء من متتالية متناقصة بطول 1 + s على الأقل.

انظر أيضا

مبرهنة رمزي

وصلات خارجية

• إيريك ويستاين، Erdős-Szekeres Theorem، ماثوورلد Mathworld (باللغة الإنكليزية).