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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
Monotone-subseq-17-5.svg

في الرياضيات، مبرهنة إيردوس-سيكريس تنص على أنه بكل متتالية بطول  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، نميز كل عدد ni في المتتالية بالزوج (ai,bi)، بحيث أن ai هو طول أطول متتالية متزايدة تنتهي بـ ni و bi هو طول أطول ممتالية متناقصة تنتهي بـ ,ni. كل عددين في المتتالية مميزين بزوج مختلف:

  • إذا كان i < j و ni < nj إذن ai < aj
  • إذا كان i < j و ni > nj إذن bi < bj

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

انظر أيضا[عدل]

مبرهنة رمزي

مراجع[عدل]

  1. ^ Steele، J. Michael (1995)، "Variations on the monotone subsequence theme of Erdős and Szekeres"، in Aldous، David؛ Diaconis، Persi؛ Spencer، Joel et al.، Discrete Probability and Algorithms، IMA Volumes in Mathematics and its Applications 72، Springer-Verlag، صفحات 111–131  .

وصلات خارجية[عدل]