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

في الرياضيات، تنص مبرهنة إيردوس-سيكريس على أنه في كل متتالية مكونة من أعداد حقيقية بطول $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) عاين ستة براهين مختلفة لمبرهنة إيردوس-سيكريس، بما في ذلك البرهان التالي. ^[1]

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

إذا كانت معطاه متتالية بطول 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 على الأقل.

انظر أيضا

مبرهنة رمزي

مراجع

^ Steele، J. Michael (1995)، "Variations on the monotone subsequence theme of Erdős and Szekeres"، في Aldous، David؛ Diaconis، Persi؛ Spencer، Joel؛ Steele، J. Michael (المحررون)، Discrete Probability and Algorithms (PDF)، IMA Volumes in Mathematics and its Applications، Springer-Verlag، ج. 72، ص. 111–131، مؤرشف من الأصل (PDF) في 2019-06-11.

وصلات خارجية

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

[steele-1] Steele، J. Michael (1995)، "Variations on the monotone subsequence theme of Erdős and Szekeres"، في Aldous، David؛ Diaconis، Persi؛ Spencer، Joel؛ Steele، J. Michael (المحررون)، Discrete Probability and Algorithms (PDF)، IMA Volumes in Mathematics and its Applications، Springer-Verlag، ج. 72، ص. 111–131، مؤرشف من الأصل (PDF) في 2019-06-11.

[1]